Graph Theory previous year questions

Question-1. Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three? [GATE 2013]

(A). 8    (B). 7    (C). 42    (D). More than 42   

Solution-1. For a cycle of 3 length, there should be 3 vertices. We have 8 vertices. So in ⁸C₃ ways we can have a cycle of length 3.But for two vertices to be connected there is a probability of 1/2.
So, Total number of such cycles are,
⁸C₃ * (1/2)³ = 7

Question-2. Which of the following statements is/are TRUE for undirected graphs? [GATE 2013]
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
(A) P only
(B) Q only
(C) Both P and Q
(D) Neither P nor Q
Solution-2. We know that sum of degree of all vertices in a graph is equal to twice of number of edges.(Handshaking Theorem)
That is, Σd(v_i) = 2*|E|
So, statement-Q is true because, sum of degrees is a multiple of 2 which is always an even number.
Now, for P, let us assume number of odd degree vertices is odd. In that case sum of degree of all vertices would be an odd number. E.g. 5,3,5 are three vertices in a graph with odd degree and rest of the vertices are of even degree. So, Even+odd+odd+odd = odd which can't be equal to 2*|E|. So Number of odd degree vertices is always even.
Both the statements - P and Q are correct.

Question-3. Maximum number of edges in a planar graph with n vertices is? [GATE 1992]
Solution-3. Since every edge contributes to two faces, and every face have at least three edges, e/3 must be greater than or equal to f/2 (e/3 denotes half of the maximum number of faces)
e/3 ≥ f/2
i.e., e ≥ 3f/2  ....(1)
By Euler's formula for planar graphs, we know,
e = n+f-2  ....(2)
By (1) and (2),  e ≥ 3(e-n+2)/2
i.e., e ≤ 3n-6
So, maximum number of edges that we can have in a planar graph with n vertices is = 3n-6 (where n = Number of vertices in graph)

Question-4. A non-planar graph with minimum number of vertices has- [GATE 1992]
(a) 9 edges, 6 vertices   (b) 6 edges, 4 vertices
(c) 10 edges, 5 vertices   (d) 9 edges, 5 vertices
Solution-4. Kuratowski's first graph, K₅ which is nothing but a complete graph of 5 vertices is a non-planner graph with minimum number of vertices. So option-(c) is the correct answer.
Please note that, A graph in which there is an edge between every pair of vertices is called as complete graph.

Question-5.Consider a simple connected graph G with n vertices and n-edges (n>2). Then, which of the following statements are true? [GATE-1993]
(a) G has no cycles.
(b) The graph obtained by removing any edge from G is not connected.
(c) G has at least one cycle.
(d) The graph obtained by removing any two edges from G is not connected.
(e) None of the above.
Solution-5. Let's assume number of edges = number of vertices = 3 Then, it would be a complete graph of 3 vertices which is a cycle of 3 vertices.
Now, let's check each option one by one.
(a)- false, because when n=3, it's a cycle (It holds for other values of n as well)
(b)- false, because if we remove an edge from G, when n=3, it is still be connected but would not be a cycle anymore.
Please note that, a graph is called connected if there's at least one path (not edge) between every pair of vertices.
(c)-true
(d)-true, you can check it on a graph where n=3
so, option-(c) & (d) are correct.