Ques 1: A graph is planar if and only if,
GATE 1990
(A) It does not contain subgraphs homeomorphic to k5 and k3,3
(B) It does not contain subgraphs isomorphic to k5 or k3,3
(C) It does not contain subgraphs isomorphic to k5 and k3,3
(D) It does not contain subgraphs homeomorphic to k5 or k3,3
Ans: (D) It does not contain subgraphs homeomorphic to k5 or k3,3
Solution: Kuratowski’s Theorem: A graph is planar if and only if, It does not contain subgraphs homeomorphic to k5 or k3,3
Ques 2: The maximum number of possible edges in an undirected graph with n vertices and k components is ______.
GATE 1991
Ans: N vertices and K components.
(Component means they are non connected subgraphs)
We want maximum edges in total graph.
To get maximum, take one vertex each for each component, except last component.
Now k−1 components have 1 vertex each and so no edges.
The last component has n−(k−1) vertices.
So make the last component complete.
i.e., It has n−(k−1)C2=(n−k)(n−k+1)/2 edges.
Ques 3: 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
Ans: (C) 10 edges, 5 vertices
Solution: A non-planar graph with minimum number of vertices has 10 edges, 5 vertices i.e K5
A non-planar graph with minimum number of edges has 9 edges, 6 vertices i.e K3,3
Ques 4: Maximum number of edges in a planar graph with n vertices is _____
GATE 1992
Ans: 3n-6
Solution: Max no of edges in connected, planar, simple graph with n vertices is 3n-6
Ques 5: How many perfect matching are there in a complete graph of 66 vertices?
GATE 2003
(A) 15
(B)24
(C) 30
(D) 60
Ans: (A) 15
Solution: For first perfect matching no of options = 5
For 2nd perfect matching no of options = 3 (two vertexes are already used)
For third perfect matching no of options = 1( 4 vertices are already used)
so total = 5 * 3 * 1 = 15
Ques 6: The number of connected components in G is:
GATE 2006
(A) n
(B) n+2
(C) 2n/2
(D) 2n/n
Ans: (B) n+ 2
Solution:It will be n+2 because ϕ and {1}{2}{3}{4}……{n} will have degree 0 and all the other will be connected into one component.
so n+2 is the answer
Ques 7: 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:
GATE 2005
(A) 0
(B) 8
(C) 9
(D) 13
Ans: (B) 8
F+V=E+2
F=E+2-V
=19+2-13
=8
Ques 8: Let G be the non-planar graph with minimum possible number of edges. Then G has
GATE 2007
(A) 9 edges, 5 vertices
(B) 9 edges, 6 vertices
(C) 10 edges, 5 vertices
(D) 10 edges, 6 vertices
Ans: (B) 9 edges, 6 vertices
Solution: A non-planar graph with minimum number of vertices has 10 edges, 5 vertices i.e K5
A non-planar graph with minimum number of edges has 9 edges, 6 vertices i.e K3,3
Ques 9: 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
GATE IT 2006
(A) HAmilton Cycle
(B) Grid
(C) Hypercube
(D) Tree
Ans: (D) Tree
Solution: Hamiltonian cycle ⇒ This is a cycle. A cycle will not only connect all vertices, it will have 1 extra edge than necessary. So I can just remove that edge & still connect all vertices. So, this is FALSE.
grid ⇒ A grid has cycles and so this is FALSE for same reason as option A.
Hypercube ⇒ A hypercube graph also has cycles. So, this also is FALSE.
Tree ⇒ This is answer. We need to have minimum spanning tree has to be exact.
“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 Minimum Spanning Tree”. So, (D) is TRUE.
Ques 10: Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from uu by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is,
GATE IT 2006
(A) 1/(2n-1)
(B) 1/n
(C) 2/n
(D) 3/n
Ans: (C) 2/n
Solution: The diameter of a graph is the length of the shortest path between the most distanced nodes
For the given condition we can simply design a K-MAP and mark an edge between every two adjacent cells in K-Map.
(adjacency has to seen just as we do for minimization )
That will give us a Bipartite graph. Chromatic number for this =2.
Also from the same, we can conclude that we need ,for a n bit string, to traverse NO MORE than (n−1) edges or ′n′ vertices to get a path b/w two arbitrary points.
So ratio is (2n)
The given graph is actually hypercubegraph.