GraphTheory
Question 1 
11 
v  e + f = 2
v is number of vertices
e is number of edges
f is number of faces including bounded and unbounded
8e+5=2
=> 132 =e
The number of edges are =11
Question 2 
Let M be the adjacency matrix of G.
Define graph G2on the same set of vertices with adjacency matrix N, where
Which one of the following statements is true?
Question 3 
The number of distinct simple graphs with upto three nodes is
15  
10  
7  
9 
Question 4 
The number of edges in a regular graph of degree d and n vertices is _________.
d*n/2 
d * n = 2 * E
∴ E = d*n/2
Question 5 
The minimum number of edges in a connected cyclic graph on n vertices is:
n  1  
n  
n + 1  
None of the above 
In cyclic graph:
No. of edges = No. of vertices
⇒ n = n
Question 6 
Prove that in finite graph, the number of vertices of odd degree is always even.
Theory Explanation. 
Question 7 
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 edgecolour G is _____.
7 
The vertex in the set of size 3 has 4 edges connected to 4 vertices on other set. So, edge color of G is max(3,4) i.e. 4.
When a vertex is added to the graph with 7 vertices ( K_{3x4} has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
Question 8 
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 
ve+f = 2
Given 10 vertices & 15 edges
1015+f = 2
f = 2+1510
f = 7
There will be an unbounded face always. So, number of faces = 6.
Question 9 
Which of the following graphs is isomorphic to
(A) 3 cycle graph not in original one.
(B) Correct 5 cycles & max degree is 4.
(C) Original graph doesn’t have a degree of 3.
(D) 4 cycles not in original one.
Question 10 
Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to
15  
30  
45  
360 
It is asked to find the distinct cycle of length 4. As it is complete graph, if we chose any two vertices, there will be an edge.
So, to get a cycle of length 4 (means selecting the 4 edges which can form a cycle) we can select any four vertices.
The number of such selection of 4 vertices from 6 vertices is ^{6}C_{4} => 15.
From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like
abcd
abdc
acbd
acdb
adbc
adcb (Total 6, which is equal to number of cyclic permutations (n1)! )
As they are labelled you can observe, abcd and adcb are same, in different directions.
So, we get only three combinations from the above 6.
So, total number of distinct cycles of length 4 will be 15*3 = 45.
If it is asked about just number of cycles then 15*6 = 90
Question 11 
Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if i  j = 8 or i  j = 12. The number of connected components in G is
8  
4  
12  
25 
1 — 9 — 17 — ......... — 97
2 — 10 — 18 — ......... — 98
3 — 11 — 19 — ......... — 99
4 — 12 — 20 — ......... — 100
5 — 13 — 21 — ......... — 93
6 — 14 — 22 — ......... — 94
7 — 15 — 23 — ......... — 95
8 — 16 — 24 — ......... — 96
We have covered all vertices using 8 vertex sets considering only i  j = 8. Using i  j = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
Question 12 
(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n3)/2.
(b) Let R be a binary relation on A = {a, b, c, d, e, f, g, h} represented by following two component digraph. Find the smallest integers m and n such that mm = R^{n}.
Theory Explanation. 
Question 13 
Let (A, *) be a semi group. Furthermore, for every a and b in A, if a ≠ b, then a*b ≠ b*a.
(a) Show that for every a in A
a*a = a
(b) Show that for every a, b in A
a*b*a = a
(c) Show that for every a, b, c in A
a*b*c = a*c
Theory Explanation. 
Question 14 
Let G be a connected, undirected graph. A cut in G is a set of edges whose removal results in 0 being broken into two or more components which are not connected with each other. The size of a cut is called its cardinality. A mencut of G is a cut in G of minimum cardinality. Consider the following graph.
(a) Which of the following sets of edges is a cut?
(i) {(A,B), (E,F), (B,D), (A,E), (A,D)}
(ii) {(B,D), (C,F), (A,B)}
(b) What is the cardinality of a mincut in the graph?
(c) Prove that if a connected undirected graph G with n vertices has a mincut of cardinality K, then G has atleast (nk/2) edges.
Theory Explanation. 
Question 15 
Let S be a set of n elements {1, 2, …., n} and G a graph with 2^{n} vertices, each vertex corresponding to a distinct subset of S. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly 2 elements. Note: The symmetric difference of two sets R^{1} and R^{2} is defined as (R^{1}/R^{2})∪(R^{2}/R^{1})
(a) Every vertex in G has the same degree. What is the degree of a vertex in G?
(b) How many connected components does G have?
Theory Explanation is given below. 
Question 16 
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v_{1}, v_{2}, ...,v_{n}} of n vertices?
n(n1)/2  
2^{n}  
n!  
2^{n(n1)/2} 
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2^{(n C 2) ⇒ 2(n(n1)/2)}
Question 17 
The minimum number of colours required to colour the vertices of a cycle with η nodes in such a way that no two adjacent nodes have the same colour is
2  
3  
4  
n  2[n/2] + 2 
Question 18 
Maximum number of edges in a nnode undirected graph without self loops is
n^{2}  
n(n1)/2  
n1  
(n+1)(n)/2 
Question 19 
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
k and n  
k – 1 and k + 1  
k – 1 and n – 1  
k + 1 and n – k 
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n1) components.
Question 20 
How many perfect matching are there in a complete graph of 6 vertices ?
15  
24  
30  
60 
(2n)!/n!×2^{n}
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×2^{3} = 15
Question 21 
A graph G = (V,E) satisfies E≤ 3V6. The mindegree of G is defined as . Therefore, mindegree of G cannot be
3  
4  
5  
6 
E ≤ 3v  6
Based on handshaking lemma, the minimum degree is (min×v)/2
⇒ (min×v)/2 ≤ 3v  6
Checking the options lets take min=6
(6×v)/2 ≤ 3v  6
0 ≤ 6 (Not satisfied)
And which is inconsistent.
Question 22 
Maximum number of edges in a planar graph with n vertices is ________
3n  6 
⇒ (3n  2) = 3n  6
Question 23 
A nonplanar graph with minimum number of vertices has
9 edges, 6 vertices  
6 edges, 4 vertices  
10 edges, 5 vertices  
9 edges, 5 vertices 
The above graph with 5 vertices and 10 edges is nonplanar.
Question 24 
Let T be a Depth First Tree of a undirected graph G. An array P indexed by vertices of G is given. P[V] is the parent of vertex V, in T. Parent of the root is the root itself.
Give a method for finding and printing the cycle formed if the edge (u,v) of G not in T (i.e., e ∈ G − T) is now added to T.
Time taken by your method must be proportional to the length of the cycle.
Describe the algorithm in a PASCAL – like language. Assume that the variables have been suitably declared.
Theory Explanation. 
Question 25 
(a) If G is a group of even order, then show that there exists an element a ≠ e, the identity in g, such that a^{2} = e
(b) Consider the set of integers {1,2,3, 4,6,8,12,24} together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?
(i) group (ii) ring (iii) field (iv) lattice
Theory Explanation. 
Question 26 
The maximum number of possible edges in an undirected graph with a vertices and k components is ________.
(nk)(nk+1)/2 
To get maximum, take one vertex each for each component, except last component.
Now, k1 components have 1 vertex each and so on edges.
The last component has (n(k1)) vertices. So make the last component complete, i.e., it has ^{n(n1)}C_{2}
= (nk)(nk+1)/2
= maximum no. of edges
Question 27 
What is the maximum number of edges in an acyclic undirected graph with n vertices?
n  1  
n  
n + 1  
2n  1 
= n  1
Question 28 
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?
10  
11  
18  
19 
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x  9) * 3 = 27 * 2
24 + (x  9) * 3 = 54
x = 19
Question 29 
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
There exists a cutset in G having all edges of maximum weight  
There exists a cycle in G having all edges of maximum weight  
Edge e cannot be contained in a cycle  
All edges in G have the same weight 
(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.
Question 30 
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is
4  
7  
23  
99 
j = i +1
(or)
j = 3i
Second option will help us reach from 1 to 100 rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.
So, the edge sequence with minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
Question 31 
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 u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
1/(2^{n1})  
1/n  
2/n  
3/n 
That will give us a bipartite graph, with chromatic number = 2
Also from the same we can conclude that we need for a 'n' bit string, to traverse no more than (n1) edges or 'n' vertices to get a path between two arbitrary points. So the ratio is (2/n).
Question 32 
What is the chromatic number of the following graph?
2  
3  
4  
5 
→ Chromatic number of a graph is the smallest number of colours needed to colour the vertices so that no two adjacent vertices share the same colour.
Question 33 
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
5  
4  
3  
2 
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
Question 34 
G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be
Regular  
Complete  
Hamiltonian  
Euler 
→ In Euler graph all degrees must be even for all nodes. And number of odd degree vertices should be even.
→ So, degree of this new node will be even and as a new edge is formed between this new node and all other nodes of odd degree hence here is not a single node exists with degree odd so this is Euler graph.
Question 35 
36 
Given 10 vertices,
Then we can have a complete graph with 9 vertices and one isolated verted.
Number of edges in complete graph with 9 edges is n(n1)/2 = 9*8/2 = 36
Question 36 
A ^3  
A^ 3 divided by 2  
A ^3 divided by 3  
A ^3 divided by 6 
Question 37 
Which of the following statements is/are TRUE?
The chromatic number of the graph is 3.  
The graph has a Hamiltonian path  
The following graph is isomorphic to the Peterson graph.  
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.) 
Peterson graph ihas hamiltonian path but not hamiltonian cycle
Given graph in option C is isomorphic as the given has same number of vertice, edges, degree sequence and cycles.
LArgest independent set can be more than 3
Question 38 
The diagonal entries of A 2 are the degrees of the vertices of the graph.  
If the graph is connected, then none of the entries of A^ n + 1 + I n can be zero.  
If the sum of all the elements of A is at most 2( n 1), then the graph must be acyclic.  
If there is at least a 1 in each of A ’s rows and columns, then the graph must be Connected. 
The entries aii show the number of 2length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3length paths between the nodes i and j.
In A^n1 + I n, we will have at least n1 length paths, so there is no possibility of zero entires
Question 39 
Which of the following graphs is/are planner?
Theory Explanation is given below. 
→ Let us assume K_{33}is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K_{33}.
Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n4.
Where m=9, n=6
⇒ 9 ≤ 12  4
⇒ 9 ≤ 8, which is to be false, then K_{33} is nonplanar graph.
(ii) G_{2} is a planar graph. Because it can be redrawn like as below.
(iii) Let us assume G_{3} be a planar graph then it also be satisfy useful corollary.
Where m=9, n=6
then 9 ≤ 124
9 ≤ 8 is False
So, G_{3} is nonplanar graph.
Answer: Only G_{2} is planar graph.
Question 40 
Choose the correct alternatives (More than one may be correct).
A graph is planar if and only if,It does not contain subgraphs homeomorphic to k_{5} and k_{3,3}.  
It does not contain subgraphs isomorphic to k_{5} or k_{3,3}.  
It does not contain a subgraph isomorphic to k_{5} or k_{3,3}.  
It does not contain a subgraph homeomorphic to k_{5} or k_{3,3}. 
Question 41 
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is
2  
3  
4  
5 
→ a, b, c, d = 4
→ The minimum no. of colours required to colour a graph = 4 (no two adjacent vertices have same colours)
Question 42 
How many graphs on n labeled vertices exist which have at least (n^{2}  3n)/2 edges?
Maximum no. of vertices = n(n1)/2 = v
No. of graphs with minimum b edges is
= C(v,e) + C(v,e+1) + C(v,e+2) + ... + C(v,v)
= C((v,ve) + C(v,v(e+1)) + C(v,v(e+2)) + ... + C(v,0)
= C(a,n) + C(a,n1) + C(a,n2) + ... + C(a,0) (since ab=n)
= C(n(n1)/2,n) + C(n(n1)/2,n1) + ... + C(n(n1)/2,0)
Question 43 
Let G_{1} = (V,E_{1}) and G_{2} = (V,E_{2}) be connected graphs on the same vertex set V with more than two vertices. If G_{1} ∩ G_{2} = (V, E_{1} ∩ E_{2}) is not a connected graph, then the graph G_{1} U G_{2} = (V, E_{1} U E_{2})
cannot have a cut vertex
 
must have a cycle  
must have a cutedge (bridge)
 
has chromatic number strictly greater than those of G_{1} and G_{2}

(A)
False, since in G_{1}∪G_{2} 'C' is a cut vertex.
(B) True, for all conditions.
(C)
False. G_{1}∪G_{2} has no bridge.
D)
False. G_{1}∪G_{2}, G_{1}, G_{2} all the three graphs have chromatic number of 2.
Question 44 
There are two elements x, y in a group (G,∗) such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that
x * x = y * y = x * y * x = y * x * y * x = e
where e is the identity element. The maximum number of elements in such a group is ________.
4  
5  
6  
7 
a*a^{1} = e
1. x*x = e So x^{1} is x ⇒ x is element of Group
2. y*y = e So y^{1} = y ⇒ y is element of Group
4. (y*x)*(y*x) = x*y*y*x = x*x*e = e So (y*x)^{1} = (y*x)
In ③, ④
x*y, y*x has same inverse, there should be unique inverse for each element.
x*y = y*x (even with cumulative law, we can conclude)
So {x, y, e, x*y} are element of Group.
Question 45 
If G is a forest with n vertices and k connected components, how many edges does G have?
⌊n/k⌋  
⌈n/k⌉  
n–k  
nk+1 
Option 1, 2 will give answer 1. (i.e. one edge among them),
Option 3: nk = 0 edges.
Option 4: nk+1 = 1 edge, which is false.
Question 46 
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
In any planar embedding, the number of faces is at least n/2 + 2  
In any planar embedding, the number of faces is less than n/2 + 2  
There is a planar embedding in which the number of faces is less than n/2 + 2  
There is a planar embedding in which the number of faces is at most n/(δ+1) 
v – e + f = 2 →①
Point ① degree of each vertex is minimum ‘3’.
3×n ≥ 2e
e ≤ 3n/2
From ① :
n3n/2+f = 2 ⇒
Question 47 
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A tree has no bridges  
A bridge cannot be part of a simple cycle  
Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph)  
A graph with bridges cannot have a cycle 
∴ (A) is false
Since, every edge in a complete graph kn(n≥3) is not a bridge ⇒
(C) is false
Let us consider the following graph G:
This graph has a bridge i.e., edge ‘e’ and a cycle of length ‘3’
∴ (D) is false
Since, in a cycle every edge is not a bridge
∴ (B) is true
Question 48 
A graph is selfcomplementary if it is isomorphic to its complement for all selfcomplementary graphs on n vertices, n is
A multiple of 4  
Even  
Odd  
Congruent to 0 mod 4, or, 1 mod 4

Question 49 
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is _______________.
24  
25  
26  
27 
V + R = E + 2 (1) where V, E, R are respectively number of vertices, edges and faces (regions)
Given V = 10 (2) and number of edges on each face is three
∴3R = 2E ⇒ R = 2/3E (3)
Substituting (2), (3) in (1), we get
10 + 2/3E = E + 2 ⇒ E/3 = 8 ⇒ E = 24
Question 50 
The minimum number of colours that is sufﬁcient to vertexcolour any planar graph is ________.
4  
5  
6  
7 
Here it is asked about the sufficient number of colors, so with the worst case of 4 colors we can color any planar graph.
Question 51 
color(v_{i}) ← min{j ε N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE?
This procedure results in a proper vertex coloring of G.  
The number of colors used is at most Δ(G) + 1.  
The number of colors used is at most Δ(G).  
The number of colors used is equal to the chromatic number of G. 
Question 52 
G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.
16  
17  
18  
19 
Degree of each vertex ≥ 3
v = 2E
The relation between max and min degree of graph are
m ≤ 2E / v ≤ M
Given minimum degree = 3
So, 3 ≤2 E / v
3v ≤ 2E
3(n) ≤ 2(25)
n ≤ 50/3
n ≤ 16.6
(n = 16)
Question 53 
The chromatic number of the following graph is _______.
1  
2  
3  
4 
Question 54 
Let G be a graph with 100! vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G.
Then, y + 10z = ___________.
109  
110  
111  
112 
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it.
So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
Question 55 
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
n!  
1  
(n1)!  
The total number of hamiltonian cycles in a complete graph are
(n1)!/2, where n is number of vertices.
Question 56 
Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
G_{1}=(V,E_{1}) where E_{1}={(u,v)(u,v)∉E}  
G_{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E}  
G_{3}=(V,E_{3}) where E_{3}={(u,v)there is a path of length≤2 from u to v in E}  
G_{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated 
→ It strongly connected.
(A) G_{1}=(V,E_{1}) where E_{1}={(u,v)(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G_{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G_{3}=(V,E_{3}) where E_{3}={(u,v)there is a path of length≤2 from u to v in E}
This can also be true.
eg:
Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G_{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated.
If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G_{4} contain only ‘1’ component, which is not same as G.
Question 57 
Consider an undirected graph where selfloops are not allowed. The vertex set of G is {(i,j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if a  c ≤ 1 and b  d ≤ 1. The number of edges in this graph is __________.
506  
507  
508  
509 
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.
From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012 = 2*E
⇒ E = 506
Question 58 
An ordered tuple (d_{1}, d_{2}, ..., d_{n}) with d_{1} ≥ d_{2} ≥ ... d_{n} is called graphic if there exists a simple undirected graph with n vertices having degrees d_{1}, d_{2}, ..., d_{n} respectively. Which of the following 6tuples is NOT graphic?
(1, 1, 1, 1, 1, 1)  
(2, 2, 2, 2, 2, 2)  
(3, 3, 3, 1, 0, 0)  
(3, 2, 1, 1, 1, 0) 
A) (1, 1, 1, 1, 1, 1)
Yes, it is a graph.
We will see that option (C) is not graphic.
Question 59 
Which of the following statements is true for every planar graph on n vertices?
The graph is connected  
The graph is Eulerian
 
The graph has a vertexcover of size at most 3n/4  
The graph has an independent set of size at least n/3

(A) Consider the following disconnected graph which is planar.
So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.
So false.
(D) Consider K_{4} graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
Question 60 
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 
F = E  V + 2 [From Euler's formula i.e., F + V  E = 2]
F = 19  13 +2
F = 8
Question 61 
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

Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices  Minimum cover of vertex G
= 20  8
= 12