# Recent questions and answers in Graph Theory

1
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
2
Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many graphs have exactly two cycles ? $\sum_{k=1}^{n-1} k!(n-k)!$ $\frac{n!}{2}\bigg[\sum_{k=1}^{n-1} \frac{1}{k(n-k)}\bigg]$ $n!\bigg[\sum_{k=1}^{n-1} \frac{1}{k}\bigg]$ $\frac{n!(n-1)}{2}$ None of the above
3
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree
4
The number of labelled subgraph possible for the graph given below are ________.
5
The maximum number of edges in a bipartite graph on $12$ vertices is____
6
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots , v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.
1 vote
7
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any road leads to at ... . Is it always possible to colour each building with either red or blue so that every road connects a red and blue building?
8
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
9
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
10
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
11
Weighted graph : Is a bi-directional graph Is directed graph Is graph in which number associated with arc Eliminates table method
12
What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms? Stack for BFS and Queue for DFS Queue for BFS and Stack for DFS Stack for BFS and Stack for DFS Queue for BFS and Queue for DFS
13
Maximum degree of any node in a simple graph with $n$ vertices is $n-1$ $n$ $n/2$ $n-2$
14
If $G$ is an undirected planar graph on $n$ vertices with $e$ edges then $e\leq n$ $e\leq 2n$ $e\leq 3n$ None of the option
15
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$
16
The following graph has no Euler circuit because It has $7$ vertices. It is even-valent (all vertices have even valence). It is not connected. It does not have a Euler circuit.
17
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$
18
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q
19
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$
20
The number of edges in a complete graph with $N$ vertices is equal to : $N (N−1)$ $2N−1$ $N−1$ $N(N−1)/2$
21
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to: $3$ $4$ $5$ $6$
22
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
23
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list representation is easier than ... matrix representation. Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
24
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
25
Choose the most appropriate definition of plane graph. A simple graph which is isomorphic to hamiltonian graph. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset $X$ and $Y$ in such a way that each edge ... . A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices. None of the option.
26
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to: $15$ $30$ $56$ $60$
27
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
28
The number of edges in a complete graph with $‘n’$ vertices is equal to : $n(n-1)$ $\large\frac{n(n-1)}{2}$ $n^2$ $2n-1$
29
The following lists are the degrees of all the vertices of a graph : $1,2,3,4,5$ $3,4,5,6,7$ $1, 4, 5, 8, 6$ $3,4,5,6$ (i) and (ii) (iii) and (iv) (iii) and (ii) (ii) and (iv)
30
Consider a Hamiltonian Graph $G$ with no loops or parallel edges and with $\left | V\left ( G \right ) \right |= n\geq 3$. The which of the following is true? $\text{deg}\left ( v \right )\geq \frac{n}{2}$ for each vertex $v\\$ ... $v$ and $w$ are not connected by an edge All of the above
31
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? I only II only Both I and II Neither I nor II
32
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
33
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.
34
what is index ?
35
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 _______
36
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is: $6$ $8$ $9$ $13$
37
The maximum number of edges in a n-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is: $12$ $8$ less than $8$ more than $12$
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$