Graph Theory · Discrete Mathematics · GATE CSE

Let $A$ be the adjacency matrix of a simple undirected graph $G$. Suppose $A$ is its own inverse. Which one of the following statements is always TRUE?

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is __________

Which of the following statements is/are TRUE for a group G?

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is __________.

Which one of the following statements is TRUE in relation to these graphs?

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is ________

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE?

The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is ________

Let G be a simple, finite, undirected graph with vertex set {$$v_1,...,v_n$$}. Let $$\Delta(G)$$ denote the maximum degree of G and let N = {1, 2, ...} denote the set of all possible colors. Color the vertices of G using the following greedy strategy:

for $$i=1,....,n$$

color($$v_i)$$ $$\leftarrow$$ min{$$j\in N$$ : no neighbour of $$v_i$$ is colored $$j$$}

Which of the following statements is/are TRUE?

Let $$U = \{ 1,2,3\} $$. Let 2$$^U$$ denote the powerset of U. Consider an undirected graph G whose vertex set is 2$$^U$$. For any $$A,B \in {2^U},(A,B)$$ is an edge in G if and only if (i) $$A \ne B$$, and (ii) either $$A \supseteq B$$ or $$B \supseteq A$$. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A).

If $$\phi$$ denotes the empty set, then the cardinality of B($$\phi$$) is ___________

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all the vertices in the graph shown above is ______

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:

diam(G) = $$\displaystyle\max_{u, x\in V}$$ {the length of shortest path between u and v}

Let M be the adjacency matrix of G.

Define graph G₂ on the same set of vertices with adjacency matrix N, where

$$N_{ij} =\left\{ {\begin{array}{*{20}{c}} {1 \ \ \text{if} \ \ {M_{ij}} > 0 \ \ \text{or} \ \ P_{ij} > 0, \ \text{where} \ \ P = {M^2}}\\ {0, \ \ \ \ \ \text{otherwise}} \end{array}} \right.$$

Which one of the following statements is true?

Let G be any connected, weighted, undirected graph.

I. G has a unique minimum spanning tree, if no two edges of G have the same weight.

II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Which of the above two statements is/are TRUE?

$$\,\,\,\,$$There is exactly one vertex $$v(e)$$ in $$L$$(G)$$ for each edge $$e$$ in $$G$$

$$\,\,\,\,$$ For any two edges $$e$$ and $$e'$$ in $$G$$, $$L(G)$$ has an edge between $$v(e)$$ and $$v(e')$$, if and only if $$e$$ and $$e'$$

$$\,\,\,\,$$ Which of the following statements is/are TRUE?

(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.

Starting with the above tree, while there remains a node $$v$$ of degree two in the tree, add an edge between the two neighbours of $$v$$ and then remove $$v$$ from the tree. How many edges will remain at the end of the process?

$${n_3}$$ can be expressed as:

the number of vertices of degree zero in $$G$$ is

The maximum degree of a vertex in $$G$$ is

(a) Which of the following sets of edges is a cut?
$$\,\,\,\,$$(i)$$\,\,\,\,\left\{ {\left( {A,\,B} \right),\left( {E,\,F} \right),\left( {B,\,D} \right),\left( {A,\,E} \right),\left( {A,\,D} \right)} \right\}$$
$$\,\,\,\,$$(ii)$$\,\,\,\,\left\{ {\left( {B,\,D} \right),\left( {C,\,F} \right),\left( {A,\,B} \right)} \right\}$$

(b) What is the cardinality of a min-cut in this graph?

(c) Prove that if a connected undirected graph $$G$$ with $$n$$ vertices has a min-cut of cardinality $$k$$, then $$G$$ has at least $$(nk/2)$$ edges.