GATE CS Graphs: Connectivity, Matching, Colouring questions

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}$ 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 …

An undirected, unweighted, simple graph $G(V, E)$ is said to be $2$-colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$. Which of the following statements about $2$-colorable graphs is/are true?

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

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 …

The number of spanning trees in a complete graph of $4$ vertices labelled $\text{A, B, C,}$ and $\text{D}$ 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?

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

Let $\text{G}$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $\text{G}$ has even weight. Which of the following statements is/are TRUE for every such graph $\text{G}$?

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 __________.

Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i=1, \ldots, n$ …

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

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

The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are $\text{TRUE}?$ The size of the largest independent set of the given graph is $3.$ (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

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

In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.

Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $$\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of vertices with adjacency matrix $N$, where …

Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to

Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $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 following statements is/are TRUE?

The chromatic number of the following graph is _____