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?

Consider a complete graph $K_n$ with $n$ vertices ( $n>4$ ). Note that multiple spanning trees can be constructed over $K_n$. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets. Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of $K_n$ ?

Let $G(V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{\prime} \subseteq V$ such that for every $(u, v) \in E, u \in V^{\prime \prime}$ or $v \in V^{\prime}$. Let the size of the smallest vertex cover in $G$ be $k$. Let $S$ be any vertex cover of size $k$.

For a vertex $v \in V$, which of the following constraints will always ensure that $v \in S$ ?

Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is $\_\_\_\_$ (answer in integer)

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.