GraphTheory
Question 1 
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 2 
The chromatic number of the following graph is _______.
1  
2  
3  
4 
Question 3 
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 4 
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 5 
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 6 
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 7 
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 8 
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 9 
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 10 
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 11 
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 12 
The maximum number of edges in a bipartite graph on 12 vertices is ______.
36  
37  
38  
39 
Total no. of edges = 6×6 = 36
Question 13 
A cycle on n vertices is isomorphic to its complement. The value of n is _____.
5  
6  
7  
8 
In a cycle of n vertices, each vertex is connected to other two vertices. So each vertex degree is 2.
When we complement it, each vertex will be connected to remaining n3 vertices ( one is self and two other vertices in actual graph).
As per given question,
n3 =2
n=5
Cycle of 5 vertices is
Complement of the above graph1 is
Graph1 and Graph2 are complement each other.
So, the value of n is 5.
Question 14 
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 15 
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 16 
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?
1/8  
1  
7  
8 
The probability that there exists one edge between two vertices = 1/2
So, the total probability that all three edges of the above exists
= 1/2 × 1/2 × 1/2 (as they are independent events)
= 1/8
Total number of ways in which we can select ‘3’ such vertices among ‘8’ vertices = ^{8}C_{3} = 56
Total number of cycles of length ‘3’ out of 8 vertices = 56 × 1/8 = 7
Question 17 
Which of the following statements is/are TRUE for undirected graphs?
 P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
P only  
Q only  
Both P and Q  
Neither P nor Q 
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 18 
The line graph L(G) of a simple graph G is defined as follows: · There is exactly one vertex v(e) in L(G) for each edge e in G. · For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e'are incident with the same vertex in G. Which of the following statements is/are TRUE?
 (P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.
P only  
P and R only  
R only  
P, Q and S only 
R) False. We can give counter example. Let G has 5 vertices and 9 edges which is planar graph. Assume degree of one vertex is 2 and of all others are 4. Now, L(G) has 9 vertices (because G has 9 edges) and 25 edges. But for a graph to be planar,
E ≤ 3v  6
For 9 vertices E ≤ 3 × 9  6
⇒ E ≤ 27  6
⇒ E ≤ 21. But L(G) has 25 edges and so is not planar.
As (R) is false, option (B) & (C) are eliminated.
Question 19 
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 20 
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 21 
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 22 
K4 and Q3 are graphs with the following structures.
Which one of the following statement is TRUE in relation to these graphs?
K4 is planar while Q3 is not  
Both K4 and Q3 are planar  
Q3 is planar while K4 is not  
Neither K4 not Q3 is planar 
Both the above graphs are planar.
Question 23 
Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then
S = 2T  
S = T  1  
S = T  
S = T + 1 
i_{d}= no. of vertices of degree ‘d’ in ‘G’
Eg:
No. of vertices with degree ‘2’ = 3
ξ(G') = 3 × 2 = '6' i.e., sum of degrees
By Handshaking Theorem,
The sum of degrees would be equal to twice the no. of edges
V = 2E
It is given that ξ(G) = ξ(S) then
Sum of degrees of vertices in G is equal to sum of degrees of vertices in S
i.e., 2*(no. of edges in G) = 2*no. of edges in S no. of edges in G = no. of edges in S
Eg:
ξ(G) = (2 × 2) + (2 × 3) = 4 + 6 = 10
ξ(S) = 2 × 5 = 10
You can observe that, though no. of vertices are different, but still no. of edges are same.
Question 24 
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
 (I) 7, 6, 5, 4, 4, 3, 2, 1
(II) 6, 6, 6, 6, 3, 3, 2, 2
(III) 7, 6, 6, 4, 4, 3, 2, 2
(IV) 8, 7, 7, 6, 4, 2, 1, 1
I and II  
III and IV  
IV only  
II and IV 
⇾ Arrange the degree of vertices in descending order
eg. d_{1}, d_{2}, d_{3}... d_{n}
⇾ Discard d_{1}, subtrack ‘1’ from the next 'd_{1}' degrees
eg:
⇒ 1 1 0 1
⇾ We should not get any negative value if its negative, this is not valid sequence
⇾ Repeat it till we get ‘0’ sequence
I. 7, 6, 5, 4, 4, 3, 2, 1
➡️5, 4, 3, 3, 2, 1, 0
➡️3, 2, 2, 1, 0, 0
➡️1, 1, 0, 0, 0
➡️0, 0, 0, 0
[valid]
II. 6, 6, 6, 6, 3, 3, 2, 2
➡️5, 5, 5, 2, 2, 1, 2
put them in descending order
➡️5, 5, 5, 2, 2, 2, 1
➡️4, 4, 1, 1, 1, 1
➡️3, 0, 0, 0, 1 (descending order)
➡️3, 1, 0, 0, 0
➡️0, 1, 1, 0
[This is not valid]
III. 7, 6, 6, 4, 4, 3, 2, 2
➡️5, 5, 3, 3, 2, 1, 1
➡️4, 2, 2, 1, 0, 1
➡️4, 2, 2, 1, 1, 0 (descending order)
➡️1, 1, 0, 0, 0
➡️0, 0, 0, 0
[valid]
IV. 8, 7, 7, 6, 4, 2, 1, 1
There is a degree ‘8’, but there are only ‘8’ vertices.
A vertex cannot have edge to itself in a simple graph. This is not valid sequence.
Question 25 
What is the chromatic number of an nvertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
2  
3  
n1  
n 
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 26 
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.

If all vertices have different degrees, then the degree sequence will be {1,2,3,....n1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n1) vertices). Degree sequence has only (n1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) Consider a triangle, all vertices has same degree, so it is false
C) Consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) Consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
Question 27 
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 28 
Let G be the nonplanar graph with the minimum possible number of edges. Then G has
9 edges and 5 vertices  
9 edges and 6 vertices  
10 edges and 5 vertices  
10 edges and 6 vertices 
if n ≥ 3 then e ≤ 3n6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5)  6
9 ≤ 15  6
9 ≤ 9
Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6)  6
9 ≤ 18  6 9 ≤ 12 Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5)  6
10 ≤ 15  6
10 ≤ 9 No, it is not planar.
So, option C is nonplanar graph.
iv) e=10, n=6
10 ≤ 3(6)  6
10 ≤ 18  6
10 ≤ 12
Yes, it is planar.
Question 29 
Which of the following graphs has an Eulerian circuit?
Any kregular graph where k is an even number.  
A complete graph on 90 vertices.  
The complement of a cycle on 25 vertices.
 
None of the above. 
→ all vertices in the graph have an "even degree".
→ And the graph must be corrected.
Now in option (C) it is saying that the complement of a cycle on 25 vertices without complement the degree of each vertex is 2.
Now since there are 25 vertices, so maximum degree of each vertex will be 24 and so in complement of cycle each vertex degree will be 24  2 = 22.
There is a theorem which says "G be a graph with n vertices and if every vertex has a degree of atleast n1/2 then G is connected."
So we can say that complement of cycle with 25 vertices fulfills both the conditions, and hence is Eulerian circuit.
Question 30 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of vertices of degree zero in G is:
1  
n  
n+1  
2^{n} 
= no. of subsets with size less than or equal to 1
= n+1, because in question it is given that the two vertices are connected if and only if the corresponding sets intersect in exactly two elements.
Question 31 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The maximum degree of a vertex in G is:
2^{n2}  
2^{n3} × 3  
2^{n1} 
(k(_{c}))_{2} 2^{nk}
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(_{c}))_{2} 2^{nk} w.r.t. k and equal to 0.
You will get k = 2/(log_{e})2 which is not an integer.
So you can see it like
∴ The maximum degree 3⋅2^{n3} at k=3 or k=4.
Question 32 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 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^{n/2}  
2^{n} / n 
While other nodes are connected so that total number of connected components is (n+1)+1
(here we are adding 1 because it is connected corresponding remaining vertices)
= n+2
Question 33 
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 34 
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
Question 35 
Which one of the following graphs is NOT planar?
G_{1}  
G_{2}  
G_{3}  
G_{4} 
which is planar
G_{3} can also be drawn as
which is planar
G_{4} can also be drawn as
which is planar
But G_{1} cannot be drawn as planar graph.
Hence, option (A) is the answer.
Question 36 
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 37 
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 38 
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 39 
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 40 
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 41 
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 42 
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 43 
Maximum number of edges in a nnode undirected graph without self loops is
n^{2}  
n(n1)/2  
n1  
(n+1)(n)/2 
Question 44 
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 45 
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 46 
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 47 
(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 48 
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 49 
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 50 
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 51 
Prove that in finite graph, the number of vertices of odd degree is always even.
Theory Explanation. 
Question 52 
The number of distinct simple graphs with upto three nodes is
15  
10  
7  
9 
Question 53 
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 54 
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 55 
Maximum number of edges in a planar graph with n vertices is ________
3n  6 
⇒ (3n  2) = 3n  6
Question 56 
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 57 
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 58 
(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 59 
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 60 
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 61 
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 62 
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 63 
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 64 
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 65 
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 66 
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 67 
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 68 
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 69 
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 70 
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 71 
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 72 
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 73 
A ^3  
A^ 3 divided by 2  
A ^3 divided by 3  
A ^3 divided by 6 
Question 74 
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 75 
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 76 
maximum of n and d  
n + d  
nd  
nd / 2 
d * n = 2 * E
∴ E = d*n/2
Question 77 
Which of the following is a valid strong component?
a, c, d  
a, b, d  
b, c, d  
a, b, c 
The graph has (a, b, d) as a strongly connected component.
Question 78 
e  
e/2  
e^{2}  
2 e 
Handshaking theorem states that the sum of degrees of the vertices of a graph is twice the number of edges.
If G=(V,E) be a graph with E edges,then
Σ deg_{G}(V) = 2E
This theorem applies even if multiple edges and loops are present.
Since the given graph is undirected, every edge contributes as twice in sum of degrees. So the sum of degrees is 2e.
Question 79 
same degree  
even degree  
odd degree  
different degree 
Proof:
→ Let G(V, E) be an Euler graph. Thus G contains an Euler line Z, which is a closed walk.
→ Let this walk start and end at the vertex u ∈ V. Since each visit of Z to an intermediate vertex v of Z contributes two to the degree of v and since Z traverses each edge exactly once, d(v) is even for every such vertex.
→ Each intermediate visit to u contributes two to the degree of u, and also the initial and ﬁnal edges of Z contribute one each to the degree of u. So the degree d(u) of u is also even.
Question 80 
n^{2}  
n(n1)/2  
n1  
n(n+1)/2 
Question 81 
Multigraph  
Non regular graph  
Regular graph  
Complete graph 
Question 82 
Path  
Walk  
Tree  
Circuit 
Let G be a graph and let there be exactly one path between every pair of vertices in G. So G is connected. Now G has no cycles, because if G contains a cycle, say between vertices u and v, then there are two distinct paths between u and v, which is a contradiction. Thus G is connected and is without cycles, therefore it is a tree.
A tree is a minimally connected graph i.e. removing a single edge will disconnect the graph. A tree with n vertices has n−1 edges and only one path exists between every pair of vertices.
Question 83 
n edges  
nk edges  
(n − k)(n − k + 1) edges  
(n − k)(n − k + 1)/2 edges 
So, G has maximum number of edges if each component is a complete graph.
Hence, the maximum possible number of edges in the graph G is:
And in every case, (n − k)(n − k + 1)/2 will be greater than or equal to the above expression.
So, at maximum, there can be (n − k)(n − k + 1)/2 edges in a simple graph with n vertices and k components.
Question 84 
k and n  
k1 and k+1  
k1 and n1  
k+1 and nk 
→ If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n1) components
Question 85 
(v+1)−k  
(v+1)/2 −k  
v−k  
v+k 
→ Suppose, if each vertex is a component, then k=v, then there will not be any edges among them. So, vk= 0 edges.
Method2:
→ According to pigeonhole principle, every component have v/k vertices.
→ Every component there will be (v/k)1 edges.
→ Total k components and edges= k*((v/k)1)
= v–k
Question 86 
n * (n1) / 2  
n * (n+1) / 2  
n^{2}  
n * (n+1) 
Question 87 
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
P only  
Q only  
Both P and Q  
Neither P nor Q 
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 88 
No bridges  
{d,e}  
{c,d}  
{c,d} and {c,f} 
Equivalently, an edge is a bridge if and only if it is not contained in any cycle.
A graph is said to be bridgeless or isthmusfree if it contains no bridges.
If we remove {d,e} edge then there is no way to reach e and the graph is disconnected.
The removal of edges {c,d} and {c,f} makes graph disconnect but this forms a cycle.
Question 89 
It has 7 vertices  
It is evenvalent(all vertices have even valence)  
It is not connected  
It does not have a Euler circuit 
Important Properties:
→ An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.
→ An undirected graph can be decomposed into edgedisjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edgedisjoint cycles and its nonzerodegree vertices belong to a single connected component.
→ An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component.
→ A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edgedisjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component.
→ A directed graph has an Eulerian trail if and only if at most one vertex has (outdegree) − (indegree) = 1, at most one vertex has (indegree) − (outdegree) = 1, every other vertex has equal indegree and outdegree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph
Question 90 
ABCDCFDEFAEA  
AEDCBAF  
AEFDCBA  
AFCDEBA 
Here, Option A: A,F and E are repeated several times.
Option B: It is not a cycle. It means, not closed walk
Option C: It is closed walk and all vertex traversed. So this is final answer.
Option D: It’s not a closed walk.
Question 91 
e<=n  
e<=2n  
e<=en  
None of the option 
v − e + f = 2.
→ For a simple, connected, planar graph with v vertices and e edges and faces, the following simple conditions hold for v ≥ 3:
Theorem 1. e ≤ 3v − 6;
Theorem 2. If there are no cycles of length 3, then e ≤ 2v − 4.
Theorem 3. f ≤ 2v − 4.
Theorem (The handshaking theorem):
Let G be an undirected graph (or multigraph) with V vertices and N edges. Then
Exercise:
Suppose a simple graph has 15 edges, 3 vertices of degree 4, and all others of degree 3. How many vertices does the graph have?
3*4+(x3)*3=30
Question 92 
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 nonempty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y  
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 
In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph.
Question 93 
The Kcoloring of an undirected graph G = (V, E) is a function
C: V ➝ {0, 1, ......, K1} such that c(u)≠c(v) for every edge (u,v) ∈ E
Which of the following is not correct?
G has no cycles of odd length
 
G has cycle of odd length
 
G is 2colorable
 
G is bipartite

• A cycle of length n ≥ 3 is 2chromatic if n is even and 3chromatic if n is odd.
• A graph is bicolourable (2chromatic) if and only if it has no odd cycles.
• A nonempty graph G is bicolourable if and only if G is bipartite
Question 94 
If a graph (G) has no loops or parallel edges and if the number of vertices(n) in the graph is n≥3, then the graph G is Hamiltonian if
 (i) deg(v) ≥ n/3 for each vertex v
(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.
(iii) E(G) ≥ 1/3(n1)(n2) + 2
Choose the correct answer for the code given below:
Code:(i) and (iii) only
 
(ii) and (iii) only
 
(iii) only
 
(ii) only 
→ Dirac's theorem on Hamiltonian cycles, the statement that an nvertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle.
→ Dirac's theorem on chordal graphs, the characterization of chordal graphs as graphs in which all minimal separators are cliques.
→ Dirac's theorem on cycles in kconnected graphs, the result that for every set of k vertices in a kvertexconnected graph there exists a cycle that passes through all the vertices in the set.
Question 95 
n1  
bn  
bn+1  
independent of "the number of nodes 
● A loop is said to be independent if it contains at least one branch which is not a part of any other independent loop.
● A network with ‘b’ branches, ‘n’ nodes and ‘L’ independent loops will satisfy the fundamental theorem of network topology.
b=L+n−1
L=b−n+1
Question 96 
Zero  
One  
n1  
n/2 
● A circuit in such a tree is impossible (unless you have some other data structure as well such as a linked list or you just program the tree so badly it ends up with circuits).
Question 97 
2chromatic  
(n/2) chromatic  
(n1) chromatic  
nChromatic 
Question 98 
2  
3  
4  
n2⌈(n/2)⌉+2 
Question 99 
r^{4}  
r^{4}4r^{3}  
r^{4}5r^{3}+8r^{2}4r  
r^{4}4r^{3}+9r^{2}3r  
r^{4}5r^{3}+10r^{2}15r 
Question 100 
3  
4  
5  
6 
‘v’ is number of vertices and ‘e’ is number of edges
‘f’ is number of faces including bounded and unbounded
10  15 + f = 2
f = 7
There is always one unbounded face, so the number of bounded faces = 6
Question 101 
E  
2E  
V  
2V 
Suppose a graph has n vertices with degrees d _{1} , d _{2} , d_{ 3} , ..., d_{ n}.
Add together all degrees to get a new number
d _{1} + d _{2} + d_{ 3} + . .. + d_{ n} = D _{v} . Then D_{ v} = 2 e .
In words, for any graph the sum of the degrees of the vertices equals twice the number of edges.
Question 102 
Euler circuit  
Hamiltonian path  
Euler Path  
Hamiltonian Circuit 
● An Euler path is a path that uses every edge of a graph exactly once. An Euler circuit is a circuit that uses every edge of a graph exactly once.
● An Euler path starts and ends at different vertices.
● An Euler circuit starts and ends at the same vertex.
Question 103 
(a,b)(e,f)  
(a,b),(a,c)  
(c,d)(d,h)  
(a,b) 
● Equivalently, an edge is a bridge if and only if it is not contained in any cycle.
● The removal of edges (a,b) and (e,f) makes graph disconnected.
Question 104 
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 
An Euler path in G is a simple path containing every edge of G exactly once.
An Euler path starts and ends at different vertices.
An Euler circuit starts and ends at the same vertex.
Question 105 
5  
6  
7  
8 
Where V is the number of vertices, E is the number of edges, and R is the number of regions.
R=2V+E=28+13=7
Question 106 
6  
8  
9  
13 
● Where V is the number of vertices, E is the number of edges, and R is the number of regions.
● R=2V+E=213+19=8
● We can also term region as face
Question 107 
28  
48  
20  
None of the option 
So, we can construct 5*8 = 40 diagonals.
But we have constructed each diagonal twice, once from each of its ends. Thus there are 20 diagonals in a regular octagon.
Question 108 
If a connected graph G has planar embedding with 4 faces and 4 vertices, then what will be the number of edges in G?
7  
6  
4  
3 
For any(connected) planar graph with v vertices, e edges and faces, we have
V  E + F = 2
= 4  E + 4 =2
E = 4  2 + 4
E = 6
Question 109 
Every cut set of a connected euler graph has____
An odd number of edges
 
At least three edges
 
An even number of edges  
A single edge 
Question 110 
A graph G is dual if and only if G is a ___
Euler graph
 
Regular graph  
Complete graph  
Planar graph

→ The correspondence between edges of G and those of G* is as follows:
if e∈E(G) lies on the boundaries of faces X and Y, then the endpts of the dual edge e*∈(G*) are the vertices x and y that represent faces X and Y of G.
Question 111 
What is the chromatic number of an nvertex simple connected graph, which does NOT contain any oddlength cycle?
N  
N1  
2  
3 
→ A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 112 
Considering an undirected graph, which of the following statements is/are true?
 (i) Number of vertices of odd degree is always even
(ii) Sum of degrees of all the vertices is always even
Neither (i) nor (ii)
 
Both (i) and (ii)  
Only (ii)  
Only (i)

True: Sum of degrees of all the vertices is always even.
Question 113 
Select the option that best describes the relationship between the following graphs:
G and H are directed  
G and H are isomorphic
 
G and H are homomorphic  
G and H are not isomorphic 
1. V(G1) = V(G2)
2. E(G1) = E(G2)
3. Degree sequences of G1 and G2 are same.
4. If the vertices {V1, V2, ... Vk} form a cycle of length K in G1, then the vertices {f(V1), f(V2), … f(Vk)} should form a cycle of length K in G2.
→ Graph G and H are having same number of vertices and edges. So, it satisfied first rule.
→ u1 degree 2, u2 degree 3, u3 degree 3, u4 degree 2, u5 degree 3, u6 degree 3.
→ V1 degree 2, V2 degree 3, V3 degree 3, V4 degree 2, V5 degree 3, V6 degree 3.
→ But it violates the property of number of cycles. The number of cycles are not same.
Question 114 
Maximum of n,d  
n+d  
nd  
nd/2 
d*n = 2*E
∴ E = (d*n)/2
Question 115 
A minimal subgraph G’ of G such that V(G’)=V(G) and G’ is connected is called:
A spanning tree
 
A connected graph
 
A directed graph
 
A biconnected component 
Question 116 
deg(v) ≥n/2 for each vertex v.  
E(G) ≥1/2(n – 1) (n – 2) + 2  
deg (v) + deg(w) ≥ n whenever v and w are not connected by an edge  
All of the above 
Question 117 
Which of the following is correct?
G _{1} contains Euler circuit and G _{2} does not contain Euler circuit.  
G _{1} does not contain Euler circuit and G _{2} contains Euler circuit.  
Both G _{1} and G_{ 2} do not contain Euler circuit.  
Both G_{ 1} and G_{ 2} contain Euler circuit. 
Step1: G1 have odd number of vertices. So, it is not euler circuit.
Step2: G2 also have odd number of vertices. So, it not euler circuit.
Question 118 
14, 14  
16, 14  
16, 4  
14, 4 
=n ^{(n2)}
= 4^{ 2}
=16
Step2: Given Bipartite graph K_{ 2,2} . To find number of spanning tree in a bipartite graph K _{m,n} having standard formula is m^{ (n1)} * n^{ (m1)} .
m=2 and n=2
= 2 ^{(21)} * 2^{ (21)}
= 2 * 2
= 4
Question 119 
2  
4  
5  
6 
Definition: A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph.
Step1: b,c,e,f is complete graph.
Step2: ‘a’ is not connected to ‘e’ and ‘b’ is not connected to ‘d’. So, it is not complete graph.
Question 120 
(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
(c) A complete graph (K_{ n} ) has a Hamilton Circuit whenever n ≥ 3.
(d) A cycle over six vertices (C _{6} ) is not a bipartite graph but a complete graph over 3 vertices is bipartite.
(a) only  
(b) and (c)  
(c) only  
(d) only 
(b)TRUE: A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
(c)TRUE: A complete graph (K _{n} ) has a Hamilton Circuit whenever n ≥ 3. (d) FALSE: A cycle over six vertices (C_{ 6} ) is not a bipartite graph but a complete graph over 3 vertices is bipartite.
Question 121 
Consider the graph given below: The two distinct sets of vertices, which make the graph bipartite are:
(v _{1} , v_{ 4} , v_{ 6} ); (v_{ 2} , v_{ }3 , v_{ 5} , v_{ 7} , v_{ 8} )  
(v _{1} , v_{ 7} , v_{ 8} ); (v_{ 2} , v_{ 3} , v_{ 5} , v_{ 6} )  
(v _{1} , v_{ 4} , v_{ 6} , v_{ 7} ); (v_{ 2} , v_{ 3} , v_{ 5} , v_{ 8} )  
(v _{1} , v_{ 4} , v_{ 6} , v_{ 7} , v_{ 8} ); (v_{ 2} , v_{ 3} , v_{ 5} ) 
→ The two sets U and V may be thought of as a coloring of the graph with two colors.
Option A: FALSE because V _{5} , V_{ 7} and V_{ 3} are adjacent. So, it not not bipartite graph.
OptionB FALSE because V _{5} , V_{ 6} and V_{ 2} are adjacent. So, it not not bipartite graph.
OptionC TRUE because it follows properties of bipartied and no two colours are adjacent.
OptionD FALSE because because V _{4} , V_{ 6} and V_{ 8} are adjacent. So, it not not bipartite graph.
Question 122 
(a)
(b)
(c)
(a) and (b)  
(b) and (c)  
(a) and (c)  
(a), (b) and (c) 
Question 123 
(a) deg (v) ≥ n / 2 for each vertex of G
(b) E(G) ≥ 1 / 2 (n  1) (n  2) + 2 edges
(c) deg (v) + deg (w) ≥ n for every n and v not connected by an edge.
(a) and (b)  
(b) and (c)  
(a) and (c)  
(a), (b) and (c) 
→ According to ore’s theorem,Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if deg v + deg w ≥ n for every pair of distinct non adjacent vertices v and w of G, then G is Hamiltonian.
→ A complete graph G of n vertices has n(n−1)/2 edges and a Hamiltonian cycle in G contains n edges. Therefore the number of edgedisjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edgedisjoint Hamiltonian cycles.
So the statement(b) is false and statement a and c are true.
Question 124 
(i) 1, 2, 3, 4, 5
(ii) 3, 4, 5, 6, 7
(iii) 1, 4, 5, 8, 6
(iv) 3, 4, 5, 6
then
(i) and (ii)  
(iii) and (iv)  
(iii) and (ii)  
(ii) and (iv) 
1. Sum of degrees of the vertices of a graph should be even.
2. Sum of degrees of the vertices of a graph is equal to twice the number of edges.
Statement(i) is violating property1.
= 1+2+3+4+5
= 15 is odd number.
Statement(ii) is violating property1.
= 3+4+5+6+7
= 25 is odd number.
Statement(iii) is violating property1.
= 1+4+5+8+6
= 24 is even number
Statement(iv) is violating property1
= 3+4+5+6
= 18 is even number
Question 125 
T is a tree  
T contains no cycles  
Every pairs of vertices in T is connected by exactly one path  
All of these 
Step1:
n= number of vertices
n1 = number of edges
Example: n=5 vertices and n1=4 edges
Step2: The above graph T won’t have cycle then we are calling as tree. Here, every pairs of vertices in T is connected by exactly one path.
Note: The above properties is nothing but minimum spanning tree properties.
Question 126 
N (N−1)  
2N−1  
N−1  
N(N−1)/2 
Question 127 
2N1  
N ^{N1}  
N ^{N2}  
2N+1 
Example:
Formula to find total number of spanning trees are N ^{N2}
=5 ^{52}
=5 ^{3}
=125
Question 128 
5  
n3  
20  
11 
Here, they are clearly mentioned that “certain tree”
The tree contain maximum n1 edges. Here, ‘n’ is number of vertices.
→ According to the handshaking lemma “sum of degrees of all vertices=2e”.
→ Two vertices of degree 4, we can write into (2*4)
→ One vertex of degree 3, we can write into (1*3)
→ One vertex of degree 2, we can write into (1*2).
→ Other vertices(X) have degree 1, we can write into (X*1)
Step1: (2*4)+(1*3)+(1*2)+(X*1)
=2(X+41) [Note: ‘X’ value is not given ]
X=7
Step2: To find total number of vertices, we are adding X+4 because they already given 4 vertices.
=X+4
=7+4
=11
Method2:
Draw according to given constraints but it not suitable for very big trees
B, C, E, F, H, I, J degree = 1
D degree = 2
A degree = 4
K degree = 4
G degree = 3
Question 129 
This graph is a __________.
Complete Graph  
Bipartite Graph  
Hamiltonian Graph  
All of the above 
OptionB: It is not Bipartite Graph because it takes more than 2 colours. Bipartite Graph have exactly 2 colours.
OptionC: Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once.
Hence, OptionC is correct answer.
Question 130 
S 1 : A solution is a subtree that has a goal node at every leaf.
S 2 : OR nodes are analogous to the branching in a deterministic environment
S 3 : AND nodes are analogous to the branching in a nondeterministic environment.
Which one of the following is true referencing the above statements?
Choose the correct answer from the code given below:
S1 False, S2 True, S3 True  
S1 True, S2 True, S3 True  
S1 False, S2 True, S3 False  
S1 True, S2 True, S3 False 
● A solution in an ANDOR tree is a sub tree whose leaves are included in the goal set
Question 131 
G has no cycles of odd length  
G has cycle of odd length  
G is 2colorable  
G is bipartite 
● A cycle of length n ≥ 3 is 2chromatic if n is even and 3chromatic if n is odd.
● A graph is bicolourable (2chromatic) if and only if it has no odd cycles.
● A nonempty graph G is bicolourable if and only if G is bipartite
Question 132 
(i) deg(v) ≥n/3 for each vertex v
(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.
(iii) E (G) ≥ 1/3 (n − 1 )(n − 2 ) + 2
(i) and (iii) only  
(ii) and (iii) only  
(iii) only  
(ii) only 
→ Dirac's theorem on chordal graphs, the characterization of chordal graphs as graphs in which all minimal separators are cliques
→ Dirac's theorem on cycles in kconnected graphs, the result that for every set of k vertices in a kvertexconnected graph there exists a cycle that passes through all the vertices in the set
Question 133 
Which one of the following graph is isomorphic to the above graph ?
→The same number of vertices, edges and degrees for corresponding vertices.
→The same number of connected components,loops and parallel edges.
The above graph each vertex having degree 3 and total number of vertices are 8. Total number of edges are 12.
OptionA: Vertex v_{5} having degree 4. So, it is not isomorphic graph.
OptionB: Vertex v_{6} having degree 4. So, it is not isomorphic graph.
OptionC: Every vertex having degree 3 and total number of edges and vertices are 12 and 8.
So, it is isomorphic.
OptionD: Vertex v_{6} having degree 4. So, it is not isomorphic graph.
Question 134 
m = 3, n = 2  
m = 2, n = 3  
m = n ≥ 2  
m = n ≥ 3 
Question 135 
Where V and E are the number of vertices and edges in graph respectively.
(a)(i), (b)(iii), (c)(iv), (d)(ii)  
(a)(i), (b)(iii), (c)(ii), (d)(iv)  
(a)(iii), (b)(i), (c)(ii), (d)(iv)  
(a)(iii), (b)(i), (c)(iv), (d)(ii) 
→ Kruskal's algorithm is a minimumspanningtree algorithm which finds an edge of the least possible weight that connects any two trees in the forest and time complexity is O(E log E)
→ A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v,u comes before v in the ordering Θ(V + E)
→ Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices
Question 136 
2451  
4950  
4851  
9900 
 Undirected graph G with 100 nodes.
 Maximum number of edges to be included in G so that the graph is not connected is ?
Step1: As per the above description, it is simple undirected graph.
For simple graph using formula standard formula is ((n1)*(n2))/2
Step2: Here, n=100
n1=99
n2=98
=((n1)(n2))/2
= (99*98)/2
= 4851
Note: The simple graph won’t have parallel edges and self loops.
Question 137 
(i) A graph in which there is a unique path between every pair of vertices is a tree.
(ii) A connected graph with e = v – 1 is a tree.
(iii) A graph with e = v – 1 that has no circuit is a tree.
Which of the above statements is/are true ?
(i) & (iii)  
(ii) & (iii)  
(i) & (ii)  
All of the above 
Tree properties:
→A graph in which there is a unique path between every pair of vertices is a tree.
→A connected graph with e = v – 1 is a tree.
→A graph with e = v – 1 that has no circuit is a tree.
Question 138 
(n – 1) (n – 2)/2 edges  
more than (n – 1) (n – 2)/2 edges  
less than (n – 1) (n – 2)/2 edges  
Σ^{k}_{i}=1 C(n_{i}, 2) edges 
Simple graph properties:
→If a graph is connected then e≥n1.
→If a graph has more than e>((n1)(n2)) / 2 then it is connected.
→The n vertex graph with the maximal number of edges that is still disconnected is a K_{n1}
→A complete graph K_{n1} with n1 vertices ((n1)(n2)) / 2 edges.
→Adding any possible edge must connect the graph, so the minimum number of edges needed to guarantee connectivity for an ‘n’ vertex graph is (((n−1)(n−2)) / 2)+1
Question 139 
K_{3, 2} or K_{5}  
K_{3, 3} and K_{6}  
K_{3, 3} or K_{5}  
K_{2, 3} and K_{5} 
Question 140 
2  
3  
4  
5 
→ The sufficient number of colors in worst case is 4 colors for any planar graph.
Question 141 
n^{2}  
n(n1)  
n(n+1)  
n(n1)/2 
Question 142 
V(G) = e+n–2  
V(G) = e–n+2  
V(G) = e+n+2  
V(G) = e–n–2 
1. The number of regions corresponds to the cyclomatic complexity
2. V(G),Flow graph is defined as V(G)=EN+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
Question 143 
M+N–C  
M–N–C  
M–N+C  
M+N+C 
→ In the spanning forest the components are represented by a set of edges, rather than a set of vertices. Any vertices in the graph that are entirely unconnected will not appear in the spanning forest.
→ In spanning forest, we will use multiple trees to represent a path through the graph.
→ Consider the below example
Number of components(C)=3
Number of vertices(N)=9
Number of Edges(M)=8
By removing two edges, we can make spanning forest in the above graph.
The number of edges can be removed to make spanning forest is MN+C=89+3=2
So option C is correct.
Question 144 
all of even degree  
all of odd degree  
of any degree  
even in number 
→ Eulerian circuit (or) Euler tour in an undirected graph is a cycle that uses each edge exactly once.
Question 145 
n(n – 1)  
n(n–1)/2  
n^{2}  
n – 1 
Question 146 
S2 : My professor teaches maths, electronics and computer science.
S3 : I have a student of maths.
S4 : Algorithm is a part of computer science.
S5 : Maths students know computer science.
What would be the chromatic number of a graph, vertices of which are the actors/entities that are involved in the sentences S1 to S5 and edgesto represent the associations/relationships amongst the entities/actors as expressed in the sentences S1 to S5 above ?
2  
3  
4  
None of these 
Question 147 
3  
4  
5  
6 
n=4
= 4(43)/2
= (4*3)/2
= 12/2
= 6
Question 148 
(i) G is a tree
(ii) There is at least one path between any two distinct vertices of G
(iii) G contains no cycles and has (n1) edges
(iv) G has n edges
(i) and (ii)  
(i) and (iii)  
(i) and (iv)  
(ii) and (iii) 
OptionB: TRUE because there is at least one path between any two distinct vertices of G. otherwise we are no calling as undirected graph.
OptionC: TRUE. If G contains no cycles and has (n1) edges.
OptionD: FALSE
Question 149 
n  
n(n – 1)/2  
n(n + 1)/2  
n^{2}/2 
Ex:
n=5 and complete graph
Using formula to find number of edges is n(n1)/2
=5*(51)/2
=(5*4)/2
=10
Question 150 
3 edges  
4 edges  
7 edges  
12 edges 
Total number of vertices= n + m
Total number of edges= m*n
Example:
Question 151 
3  
0  
5  
4 
Question 152 
Descriptive Explanation 
Thus the number of required paths is
This expands to
40320 · 1 + 5040 · 7 + 720 · 21 + 120 · 35 + 24 · 35 + 6 · 21 + 2 · 7 + 1 · 1 = 95901.
Question 153 
Descriptive Explanation 
Question 154 
There is a red coloured edge.  
Any vertex that is the endpoint of a red coloured edge is also the endpoint of a green coloured edge.  
There is a vertex that is not an endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge.  
(a) and (c). 
∀x. [r(x) =⇒ b(x) ∨ ¬g(x)]
If a graph G does not satisfy the above property, then it means that there exists a vertex v satisfying
r(v) ∧ ¬b(v) ∧ g(v).
This is exactly what is stated in option (c).
Option (b) is not valid. Consider the graph G with vertex set V = {1, 2, 3} and (colored) edges given by
E = {((1, 2), red), ((1, 3), red), ((2, 3), green)}.
Vertex 3 witnesses the violation of the property P , but vertex 2 violates option (b).
Since (c) implies (a), (d) is the correct answer.
Question 155 
Find a spanning tree with minimum number of edges.  
Find a minimal colouring.  
Find a minimum size vertex cover.  
Find a maximum size independent set. 
Question 156 
5  
6  
7  
8 
Question 157 
Find a spanning tree with minimum number of edges.  
Find a spanning tree with minimum cost.  
Find a minimal colouring.  
Find a minimum size vertex cover. 
Question 158 
I only  
II only  
Both I and II  
Neither I nor II 
As a counterexample to II, take, for instance a cycle on n − k vertices u 1 , . . . , u n−k (k to be fixed). Take a vertex v _{0} and connect it to all the n − k cycle vertices to obtain a wheel with n − k + 1 vertices. Now take k − 1 vertices v _{1} , . . . , v_{ k−1} . For each i in [1, . . . , k − 1] connect v_{ i} to k + 3 equally spaced vertices C _{v i }on the cycle so that C _{v i } is connected to u _{i} , u_{ i}+b((n−k)/(k+3)c , .
Thus there are (n − k) + 1 + (k − p 1) = n vertices and (n − k) + (n − k) + (k − 1)(k + 3) = 2n − 3 + k ^{2} = 4n − 16 for k =roof of (2n − 13)
Each u _{i} is at distance exactly 2 from each of its nonneighbours on the cycle (via v_{ 0} ) for (n − k − 3) = Ω(n) vertices at distance 2. Each v j is at distance exactly 2 from at least all the other v _{k} vertices (plus at least 2ku_{ i} vertices if j not equal to 0) for at least k − 1 = Ω(sqrt(n)) vertices at distance 2.
Question 159 
Descriptive Explanation 
(b) If we root the tree at any node, we can colour the tree level by level by alternating two colours. This 2colouring gives us the partition of the vertex set
Question 160 
n(n1)  
n(n1)/2  
n^{2}  
2n1 
Question 161 
60 edges and 20 vertices.  
30 edges and 20 vertices.  
60 edges and 50 vertices.  
30 edges and 50 vertices. 
Question 162 
34  
32  
17  
16 
Question 163 
Explanation 
Pick an arbitrary vertex v _{1} in the first step. At each subsequent step, let v _{t} be the vertex picked last. If all neighbours of v_{ t} have already been picked, stop. Otherwise v_{ t+1} is chosen to be an arbitrary neighbour of v_{ t} hitherto unpicked.
Since the graph is finite, the above procedure terminates eventually. Let π = v _{1} · · · v_{ t} be the path produced at the end. By construction, it is a simple path. It follows that all neighbours of v _{t} have already been picked and they occur among {v _{1} , . . . , v_{ t−1} }. Since the minimum degree of the graph is k, it follows that k ≤ t − 1. Thus there are at least k + 1 vertices and hence at least k edges in π.
Let i be the least index such that v _{i} is adjacent to v _{t} . It is clear that the path from v_{ i} to v_{ t} is of length at least k. Adding the edge (v _{i} , v_{ t} ) yields a simple cycle of length at least k + 1.
Question 164 
Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.
Explanation 
Question 165 
2  
1  
0  
1 
Question 166 
To do this, you decide to model the problem as a graph where the nodes are the events and edges represent pairs of events where the team that you plan to send shares a member. In this setting, the graph theoretic question to be answered is:
Find a maximum length simple cycle  
Find a maximum size independent set  
Find a maximum matching  
Find a maximal connected component 
Question 167 
(a) Prove that if G has more than edges then G is connected.
(b) For every n > 2, find a graph G _{n} which has exactly n vertices and edges,and is not connected.
Descriptive Explanation 
Question 168 
6  
8  
12  
10 
Since each vertex has degree 4, the sum of the degrees is 24.
By the handshaking theorem, 2e = 24 .
so, e = 12.
r = 12−6 + 2
r = 8
Thus we have 8 regions in this planar graph.
Question 169 
m≠n, m, n≥2  
m≠n, m, n≥3  
m=n, m, n≥2  
m=2, m, n≥3 
Then A=B
That is, there is the same number of vertices in A as there are in B.
Question 170 
There is a path from vertex 1 to vertex n  
There is a path from vertex 1 to each vertex 2, . . ., n − 1  
Vertex n has degree 1  
The diameter of the graph is at most n/10  
All of the above choices must be TRUE 
Question 171 
12.11  
11.12  
10.11  
9.10 
Question 172 
If (u, v) ∈ E then u ∈ V’ and v ∈ V’  
If (u, v) ∈ E then u ∈ V’ or v ∈ V’  
Each pair of vertices in V’ is connected by an edge  
All pairs of vertices in V’ are not connected by an edge 
Question 173 
None of the above 
Question 174 
Let k_{2,2} be a complex bipartite graph given below. Which of the following is the total number of paths of length 3 from vertex 1 to vertex 4?
2  
3  
4  
1 
Question 175 
[(n2)(n1)/2]+1  
[(nk)(nk+1)]/2  
n^{2}  
[(n)(n1)]/2 
Question 176 
Biconnected graph  
Separable graph  
Forest  
Diagraph 
Question 177 
nc  
c  
c(n1)  
n/c 
Question 178 
For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is
2n  
(2n1)/2
 
2e  
e2/2 
Question 179 
The complete graph Kn has _______ different spanning trees.
n^{n2}  
n×n  
n^{n}  
n^{2} 
Question 180 
Which of the following is not a type of graph?
Euler  
Hamiltonian  
Tree  
Path 
Question 181 
If G is an undirected planar graph on n vertices with e edges then?
e<=n  
e<=2n  
e<=3n  
None of the given options 
Where r = no. of regions
From these we get e <= 3n  6
Now 2n <= 3n  6 for all vertices n >= 3
So e <= 2n is the answer.
Question 182 
___ of graph is a vertex whose removal disconnects graph
Start vertex
 
Middle point
 
Terminal vertex
 
Articulation point/Cut vertex

Question 183 
A vertex of how many degree is isolated?
0  
1  
2  
3 
Question 184 
A closed path with no other repeated vertices than the starting and ending vertices is known as
Steiner tree
 
Cycle  
Complement graph
 
Spanning tree

Question 185 
A tree contains a cycle
 
Every tree is a graph
 
A tree with N nodes contain N1 edges  
All the above

Question 186 
T is a tree  
T contains no cycles
 
Every pair of vertices in T is connected by exactly one path  
Addition of a new edge will create a cycle 
Question 187 
Both are planar  
Neither is planar  
Both are isomorphic  
None of these

The graph k(2,n) is planar for all n.
Every other case deals with k(n,m) where n,m>=3, but then this graph must have k(3,3) as a subgraph and it is nonplanar by kuratowski’s theorem.
Hence K(3,3) is not planar where as k(2,4) is planar.
Question 188 
Strongly Connected  
Connected  
Weakly Connected  
All the above 
Question 189 
D  
H  
I  
M 
Question 190 
Descriptive Explanation 
We can now follow a simple strategy: pick an arbitrary vertex, then exclude everything else in the sphere of radius 2 around the picked vertex. The sphere will have at most r_{2} + 1 vertices, of which we have picked one. We continue similarly for the remaining vertices to pick at least n/(r_{2}+1) vertices. From any friend circle, if we have picked one person, all others in that circle are excluded (since they are within distance 2), and thus our restriction for the party game is satisfied.
Question 191 
Descriptive Explanation 
Question 192 
d divides n  
Both d and n are even  
Both d and n are odd  
At least one of d and n is odd  
At least one of d and n is even 
Question 193 
An arborescence in G rooted at r is a subgraph H of G in which every vertex u ∈ V \ { r } has a directed path to the special vertex r.
The weight of an arborescence H is the sum of the weights of the edges in H.
Let H^{∗} be a minimum weight arborescence rooted at r, and w^{∗} the weight of H^{∗}. Which of the following is NOT always true?
H^{∗} has exactly n − 1 edges  
H^{∗} is acyclic  
w^{∗} is less than the weight of the minimum weight directed Hamiltonian cycle in
G, whenever G has a directed Hamiltonian cycle

Question 194 
a  
b  
c  
d  
None of the above 
Question 196 
only (i)  
only (i) and (ii)  
only (i) and (iii)  
only (ii) and (iii)  
(i), (ii), and (iii) 
Question 197 
n  
n(n1)/2  
n!  
2^{n}  
2^{m} ,where m=n(n1)/2 
Question 198 
the line graph for a complete graph is complete  
the line graph for a connected graph is connected  
the line graph for a bipartite graph is bipartite  
the maximum degree of any vertex in the line graph is at most the maximum degree in the original graph  
each vertex in the line graph has degree one or two 
Question 199 
K_{9,9}  
K_{8,8}  
K_{12,12}  
K_{9}  
The graph G on vertex set {1, 2, . . . , 9} with edge set E(G) = {{i, j} : 1 ≤ i < j ≤ 5 or 5 ≤ i < j ≤ 9}. 
Question 200 
G is V colourable  
G is 2colourable iff there are no odd cycles in G  
G is (∆ + 1)colourable where ∆ is the maximum degree in G  
There is a polynomial time algorithm to check if G is 2colourable  
If G has no triangle then it is 3colourable

Question 201 
All of (i), (ii), (iii), (iv) are possible  
(i), (ii), (iii) are possible but not (iv)  
(i) and (iv) are possible but neither (ii) nor (iii)  
(ii) and (iv) are possible but neither (i) nor (iii)  
(iii) and (iv) are possible but neither (i) nor (ii) 
Question 202 
a  
b  
c  
d  
e 
Question 203 
There are even number of vertices of even degree  
There are odd number of vertices of even degree  
There are even number of vertices of odd degree  
There are odd number of vertices of odd degree  
All the vertices are of even degree 
Question 204 
Only (1)  
Only (2)  
Only (2) and (3)  
None of (1),(2), (3)  
All of (1), (2), (3)

Question 205 
Checking if G has an Eulerian cycle can be done in polynomial time  
Deciding if G has a Hamiltonian cycle is not NPcomplete  
If G has an Eulerian cycle, then it has a Hamiltonian cycle  
A complete graph always has both an Eulerian cycle and a Hamiltonian cycle  
All of the other statements are true 
Question 206 
7  
10  
12  
17 
No. of graphs with 2 vertces and no edges = 1
No. of graphs with 2 vertices and 1 edges = 1
No. of graphs with 3 vertices and 0 edges = 1
No. of graphs with 3 vertices and 1 edges = C(3,1) ,because since the vertices are labelled so all the edges will be cosidered different.Hence no. of ways of selecting one edges out of 3 edges is =C(3,1) =3
No. of graphs with 3 vertices and 2 edges = C(3,2) = 3
No. of graphs with 3 vertices and 3 edges = C(3,3)=1
Hence total no. of subgraphs possible is = 11.But since none of the option matches so you can remove the complete graph itself.So total no. of subgraphs is 111 = 10
Question 207 
268  
9045  
270  
135 
Question 208 
Weight of (u, v) ≤ 21  
Weight of (u, v) = 21  
Weight of (u, v) ≥ 21
 
Nothing can be said about the weight of (u,v) 
Question 209 
3, 3, 3, 2, 2, 1  
3, 3, 3, 3, 2, 2  
3, 3, 3, 2, 2, 2  
3, 2, 2, 2, 2, 1 
Question 210 
7  
6  
9  
8 
Question 211 
The adjacency matrix of the following graph is:
All of the above 
Question 212 
What is true for the following graphs
(i) is planar but (ii) is not
 
Both are planar
 
(ii) is planar but (i) is not  
Both are not planar 
Yes, it is planar. Let's check for graph 2nd,
Yes, it is also planar.
Question 213 
Even number of nodes with even degree  
Even number of nodes with odd degree  
Odd number of nodes with even degree  
Odd number of nodes with odd degree 
Question 214 
e  v + 1 where e < v  
e  v + 1 where e >= v
 
v  e + 1 where e < v
 
v  e + 1 where e >=v

Question 215 
Eulerian circuit need not exist
 
Eulerian circuit exist with weight greater than 1000  
Eulerian circuit exist with weight less than 1000  
Eulerian circuit exist with weight equal to 1000 
Question 216 
3  
0  
5  
4 
Lets check taking option B,
The degree sequence is 7,6,5,4,3,2,1,0. By using havel hakemi theorem this sequence is not possible.Hence option B is not correct.
Lets check taking option D,
The degree sequence is 7,6,5,4,4,3,2,1. By using havel hakemi theorem this sequence is possible.Hence the correct answer is option D.
Question 217 
15  
24  
25  
Insufficient data 
Where,
n=no. of vertices=15
e=no. of edges
f=no. of regions=12
Hence no. of edges is ,
ne+f = 2
=>15e+12=2
=>27e=2
=>e=25
Question 218 
K_{n} has n(n1)/2 edges
 
K_{n} is Eulerian for all n ≥ 5  
K_{n} is Hamiltonian for all n ≥ 5  
K_{n} is Nonplanar for all n ≥ 5

Question 219 
n+m  
n  
m  
nm 
Question 220 
5,4,4,3,2,1  
5,4,4,3,2,2  
5,4,4,3,2,0  
7,5,1,4,2,2 
Question 221 
it is a planar graph  
it requires three colours to be minimally coloured  
it is nonplanar  
it is isomorphic to K(2,4) 
Question 222 
Every fully connected graph is a tree  
Every minimally connected graph is a tree  
Every graph with n nodes and n1 edges is a tree  
Every connected graph with no cycles is a tree 
B is true.Tree is a connected graph with minimum no. of edges.
C is false because in this statement ‘connected’ word is not used ,so a graph with n vertices and n1 edges can have cycles if the graph is disconnected.
D is true.
Question 223 
12  
10  
8  
Cannot be computed 
In a tree of n vertices no. of edges is n1.
So for given tree no. of edges is (9 + x  1) = 8 + x
Now,
Sum of degree of vertices = 2 × no. of edges
x × 1 + 2 × 2 + 4 × 3 + 3 × 4 = 2(8 + x)
x + 4 + 12 + 12 = 16 + 2x
x + 28 = 16 + 2x
12 = x
∴ x = 12
Question 224 
(2, 3, 3, 4, 4, 5)  
(2, 3, 4, 4, 5)  
(1, 3, 3, 3)  
(1, 2, 2, 2,3) 
Question 225 
^{n}C_{2}  
⌊n^2/4 ⌋  
⌊n^2/2⌋  
⌊n/2⌋ 
Question 226 
n+1  
n1  
n  
None of the above 
So if each vertex is visited exactly once then to cover those vertices exactly n1 edges are required,because if vertices are not repeated then edge will also be not repeated.
Question 227 
n1  
3n  
^{n}C_{2}  
n(n  1) 
Question 228 
n1  
⌊n/2⌋ * ⌈n/2⌉  
^{n}C_{2}  
n(n  1) 
Question 229 
(a) Does there exist a graph G with at least two vertices such that both G and G are disconnected? Justify your answer.
(b) Give an example of a graph G on four vertices such that G is isomorphic to its complement G.
(c) Does there exist a graph G with at least two vertices such that both G and G are connected? Justify your answer.
Descriptive Explanation 
Let x, y be any two vertices in G. If one of these is in Cu and the other is in R then (as shown above) {x, y} is an edge in G. If both x and y are in Cu then {x, v} and {y, v} are edges in G. If both x and y are in R then {x, u} and {y, u} are edges in G. Thus there is a (short!) path between every pair of vertices in G, and so G is connected.
(b) We take G = (V, E) where V = {v1, v2, v3, v4} and E = {{v1, v2}, {v2, v3}, {v3, v4}}. G = (V, F) where F = {{v1, v3}, {v1, v4}, {v2, v4}}. G is isomorphic to G, as given by the map {v1 7→ v2, v2 7→ v4, v3 7→ v1, v4 7→ v3}. (c) Yes. G from part (b) is an example.
Question 230 
Descriptive Explanation 
Question 231 
(i)If each vertex of a graph G has degree at least 2 then G contains a cycle as a subgraph.
(ii)If the number of edges of a graph G is at least as large as the number of its vertices, then G contains a cycle as a subgraph.
Which of the above two statements holds for all graphs?
(i) only  
(ii) only  
both (i) and (ii)  
neither of them 
(ii) Suppose not, and let H be a graph with the smallest number of vertices which contradicts the statement. That is, H has at least as many edges as vertices, and does not contain a cycle. From the solution to part (a) above we get that there must be a vertex v in H whose degree is at most one. Deleting v from H results in a graph H′ with
(i) one fewer vertex, and
(ii) at most one fewer edge, so H′ also satisfies the premise of the statement.
But then H′ does not have any cycle, because H did not have any by assumption. Thus H′ is a graph with fewer vertices than H for which the statement holds, which contradicts our assumption about H. Hence proved.
Question 232 
Harry wishes to color every wall with colors such that walls that meet at a corner get different colors. Harry also wishes to color every room so that adjacent rooms get different colors. What is the minimum number of colors to accomplish this?
4 colors for walls and 4 colors for the rooms  
3 colors for walls and 4 colors for the rooms  
2 colors for walls and 3 colors for the rooms  
2 colors for walls and 5 colors for the rooms 
Consider the undirected graph G′ where every region(polygon in the above image) is a vertex and there is an edge between two vertices whenever the regions share a boundary. Now, coloring the rooms is the same as coloring the vertices of G′ such that no two adjacent vertices get the same color. This can be done using 4 colors. Interestingly, note that you can draw G′ on paper (or a plane) such that no two edges cross each other. Such a graph is said to be a planar graph. The question is a rephrasing of the Planar 4Color Theorem.
Question 233 
Each of H1, H2 must necessarily have an odd number of vertices.
To disprove this statement, it suffices to exhibit a graph which contradicts the statement. A proof must take the form of an argument.
Descriptive explanation 
Question 234 
Descriptive Explanation 
Question 235 
1  
2  
3  
4  
5 
Question 236 
(1) M is a maximum matching in G.
(2) C is a minimum vertex cover in G.
(3) G is a bipartite graph.
Which of the following is TRUE?
Only statement (1) is correct  
Only statement (2) is correct  
Only statement (3) is correct  
Only statements (1) and (2) are correct  
All the three statements (1), (2), and (3) are correct 