Graph-Theory

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

A
n!
B
1
C
(n-1)!
D
       Engineering-Mathematics       Graph-Theory       GATE 2019       Video-Explanation
Question 1 Explanation: 
A Hamiltonian cycle is a closed loop on a graph where every node (vertex) is visited exactly once.
The total number of hamiltonian cycles in a complete graph are
(n-1)!/2, where n is number of vertices.
Question 2

The chromatic number of the following graph is _______.

A
1
B
2
C
3
D
4
       Engineering-Mathematics       Graph-Theory       GATE 2018       Video-Explanation
Question 2 Explanation: 
Chromatic number of the following graph is “3”
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 = ___________.

A
109
B
110
C
111
D
112
       Engineering-Mathematics       Graph-Theory       GATE 2018       Video-Explanation
Question 3 Explanation: 
G is a graph with 100! vertices. Label of each vertex obtains from distinct permutation of numbers “1, 2, … 100”.
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 ___________.

A
16
B
17
C
18
D
19
       Engineering-Mathematics       Graph-Theory       GATE 2017 [Set-2]       Video-Explanation
Question 4 Explanation: 
An undirected graph ‘G’ has ‘n’ vertices & 25 edges.
Degree of each vertex ≥ 3

|v| = 2|E|
The relation between max and min degree of graph are
m ≤ 2|E| / |v| ≤ M
Given minimum degree = 3
So, 3 ≤2 |E| / |v|
3|v| ≤ 2|E|
3(n) ≤ 2(25)
n ≤ 50/3
n ≤ 16.6
(n = 16)
Question 5

The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

A
4
B
5
C
6
D
7
       Engineering-Mathematics       Graph-Theory       GATE 2016 [Set-2]       Video-Explanation
Question 5 Explanation: 
The 4-colour theorem of the planar graph describes that any planar can atmost be colored with 4 colors.
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 _______________.

A
24
B
25
C
26
D
27
       Engineering-Mathematics       Graph-Theory       GATE 2015 [Set-1]
Question 6 Explanation: 
By Euler’s formula,
|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
∴3|R| = 2|E| ⇒ |R| = 2/3|E| ------(3)
Substituting (2), (3) in (1), we get
10 + 2/3|E| = |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
A tree has no bridges
B
A bridge cannot be part of a simple cycle
C
Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph)
D
A graph with bridges cannot have a cycle
       Engineering-Mathematics       Graph-Theory       GATE 2015 [Set-2]
Question 7 Explanation: 
Since, every edge in a tree is bridge
∴ (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 self-complementary if it is isomorphic to its complement for all self-complementary graphs on n vertices, n is

A
A multiple of 4
B
Even
C
Odd
D
Congruent to 0 mod 4, or, 1 mod 4
       Engineering-Mathematics       Graph-Theory       GATE 2015 [Set-2]
Question 8 Explanation: 
An n vertex self-complementary graph has exactly half number of edges of the complete graph i.e., n(n-1)/4 edges. Since n(n – 1) must be divisible by 4, n must be congruent to 0 or 1 module 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?

A
G1=(V,E1) where E1={(u,v)|(u,v)∉E}
B
G2=(V,E2 )where E2={(u,v)│(u,v)∈E}
C
G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E}
D
G4=(V4,E) where V4 is the set of vertices in G which are not isolated
       Engineering-Mathematics       Graph-Theory       GATE 2014 [Set-1]
Question 9 Explanation: 
G(V, E) is a directed graph.
→ It strongly connected.
(A) G1=(V,E1) where E1={(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) G2=(V,E2 )where E2={(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) G3=(V,E3) where E3={(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) G4=(V4,E) where V4 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
G4 contain only ‘1’ component, which is not same as G.
Question 10

Consider an undirected graph where self-loops 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 __________.

A
506
B
507
C
508
D
509
       Engineering-Mathematics       Graph-Theory       GATE 2014 [Set-1]
Question 10 Explanation: 
The total number of vertices in the graph is 12*12 = 144. The vertices are allowed to connect in both horizontal and vertical directions which are separated by at most 1 distance.
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 (d1, d2, ..., dn) with d1 ≥ d2 ≥ ... dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, ..., dn respectively. Which of the following 6-tuples is NOT graphic?

A
(1, 1, 1, 1, 1, 1)
B
(2, 2, 2, 2, 2, 2)
C
(3, 3, 3, 1, 0, 0)
D
(3, 2, 1, 1, 1, 0)
       Engineering-Mathematics       Graph-Theory       GATE 2014 [Set-1]
Question 11 Explanation: 
This can be checked by Havel-hakimi theorem:
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 ______.

A
36
B
37
C
38
D
39
       Engineering-Mathematics       Graph-Theory       GATE 2014 [Set-2]
Question 12 Explanation: 
Max. no. of edges possible in bipartite graph, only if vertices are equal in each set i.e., 12/2 = 6 in each set.

Total no. of edges = 6×6 = 36
Question 13

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

A
5
B
6
C
7
D
8
       Engineering-Mathematics       Graph-Theory       GATE 2014 [Set-2]
Question 13 Explanation: 
Complement of a graph means, we need to remove the existing edges from the graph and place the new edges which were not earlier among the actual graph.
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 n-3 vertices ( one is self and two other vertices in actual graph).
As per given question,
n-3 =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 ________.

A
4
B
5
C
6
D
7
       Engineering-Mathematics       Graph-Theory       GATE 2014 [Set-3]
Question 14 Explanation: 
We know
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?

A
⌊n/k⌋
B
⌈n/k⌉
C
n–k
D
n-k+1
       Engineering-Mathematics       Graph-Theory       GATE 2014 [Set-3]
Question 15 Explanation: 
Suppose, if each vertex is a component, then k=n, then there will not be any edges among them Replace the same in options
Option 1, 2 will give answer 1. (i.e. one edge among them),
Option 3: n-k = 0 edges.
Option 4: n-k+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?

A
1/8
B
1
C
7
D
8
       Algorithms       Graph-Theory       GATE 2013
Question 16 Explanation: 
Among available ‘8’ vertices, we need to identify the cycles of length ‘3’.

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 = 8C3 = 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.
A
P only
B
Q only
C
Both P and Q
D
Neither P nor Q
       Algorithms       Graph-Theory       GATE 2013
Question 17 Explanation: 
Euler’s Theorem 3:
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.
A
P only
B
P and R only
C
R only
D
P, Q and S only
       Algorithms       Graph-Theory       GATE 2013
Question 18 Explanation: 
P) True. Because every edge in cycle graph will become a vertex in new graph L(G) and every vertex of cycle graph will become an edge in new graph.
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| ≤ 3|v| - 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

A
3
B
4
C
5
D
6
       Engineering-Mathematics       Graph-Theory       GATE 2012
Question 19 Explanation: 
If the graph is planar, then we have to consider Euler’s formula
v-e+f = 2
Given 10 vertices & 15 edges
10-15+f = 2
f = 2+15-10
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
B
C
D
       Engineering-Mathematics       Graph-Theory       GATE 2012
Question 20 Explanation: 
Original graph:

(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

A
15
B
30
C
45
D
360
       Engineering-Mathematics       Graph-Theory       GATE 2012
Question 21 Explanation: 
Complete graph means there exists an edge between every pair of vertices.
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 6C4 => 15.
From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like
a-b-c-d
a-b-d-c
a-c-b-d
a-c-d-b
a-d-b-c
a-d-c-b (Total 6, which is equal to number of cyclic permutations (n-1)! )
As they are labelled you can observe, a-b-c-d and a-d-c-b 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?

A
K4 is planar while Q3 is not
B
Both K4 and Q3 are planar
C
Q3 is planar while K4 is not
D
Neither K4 not Q3 is planar
       Engineering-Mathematics        Graph-Theory       GATE 2011
Question 22 Explanation: 

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

A
|S| = 2|T|
B
|S| = |T| - 1
C
|S| = |T|
D
|S| = |T| + 1
       Engineering-Mathematics       Graph-Theory       GATE 2010
Question 23 Explanation: 

id= 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| = 2|E|
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
A
I and II
B
III and IV
C
IV only
D
II and IV
       Engineering-Mathematics       Graph-Theory       GATE 2010
Question 24 Explanation: 
Havel Hakimi theorem:
⇾ Arrange the degree of vertices in descending order
eg. d1, d2, d3... dn
⇾ Discard d1, subtrack ‘1’ from the next 'd1' 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 n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.

A
2
B
3
C
n-1
D
n
       Engineering-Mathematics       Graph-Theory       GATE 2009
Question 25 Explanation: 
If n≥ 2 and there are no odd length cycles, then it is a bipartite graph. 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 26

Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?

A
No two vertices have the same degree.
B
At least two vertices have the same degree.
C
At least three vertices have the same degree.
D
All vertices have the same degree.
       Engineering-Mathematics       Graph-Theory       GATE 2009
Question 26 Explanation: 
Method 1:
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n-1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n-1) vertices). Degree sequence has only (n-1) 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?

A
The graph is connected
B
The graph is Eulerian
C
The graph has a vertex-cover of size at most 3n/4
D
The graph has an independent set of size at least n/3
       Engineering-Mathematics       Graph-Theory       GATE 2008
Question 27 Explanation: 
Lets do with elimination method,
(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 K4 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 non-planar graph with the minimum possible number of edges. Then G has

A
9 edges and 5 vertices
B
9 edges and 6 vertices
C
10 edges and 5 vertices
D
10 edges and 6 vertices
       Engineering-Mathematics       Graph-Theory       GATE 2007
Question 28 Explanation: 
Using Euler’s formula we know that,
if n ≥ 3 then e ≤ 3n-6 (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 non-planar 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?

A
Any k-regular graph where k is an even number.
B
A complete graph on 90 vertices.
C
The complement of a cycle on 25 vertices.
D
None of the above.
       Engineering-Mathematics       Graph-Theory       GATE 2007
Question 29 Explanation: 
Two necessary condition for the existence of Eulerian circuits is
→ 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 n-1/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 2n 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:

A
1
B
n
C
n+1
D
2n
       Engineering-Mathematics       Graph-Theory       GATE 2006
Question 30 Explanation: 
No. of vertices with degree zero is
= 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 2n 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:

A
B
2n-2
C
2n-3 × 3
D
2n-1
       Engineering-Mathematics       Graph-Theory       GATE 2006
Question 31 Explanation: 
The degree of each subset with k elements will be
(k(c))2 2n-k
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(c))2 2n-k w.r.t. k and equal to 0.
You will get k = 2/(loge)2 which is not an integer.
So you can see it like

∴ The maximum degree 3⋅2n-3 at k=3 or k=4.
Question 32

The 2n 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:

A
n
B
n+2
C
2n/2
D
2n / n
       Engineering-Mathematics       Graph-Theory       GATE 2006
Question 32 Explanation: 
Not connected nodes is n+1.
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:

A
6
B
8
C
9
D
13
       Engineering-Mathematics       Graph-Theory       GATE 2005
Question 33 Explanation: 
No. of faces in a planar embedding of a graph is
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

A
12
B
8
C
Less than 8
D
More than 12
       Engineering-Mathematics       Graph-Theory       GATE 2005
Question 34 Explanation: 
No. of vertices = 20
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?

A
G1
B
G2
C
G3
D
G4
       Engineering-Mathematics       Graph-Theory       GATE 2005
Question 35 Explanation: 
G2 can also be drawn as

which is planar
G3 can also be drawn as

which is planar
G4 can also be drawn as

which is planar
But G1 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

A
2
B
3
C
4
D
5
       Engineering-Mathematics       Graph-Theory       GATE 2004
Question 36 Explanation: 

→ 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 (n2 - 3n)/2 edges?

A
B
C
D
       Engineering-Mathematics       Graph-Theory       GATE 2004
Question 37 Explanation: 
No. of atleast edges = (n2-3n)/2 = e
Maximum no. of vertices = n(n-1)/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,v-e) + C(v,v-(e+1)) + C(v,v-(e+2)) + ... + C(v,0)
= C(a,n) + C(a,n-1) + C(a,n-2) + ... + C(a,0) (since a-b=n)
= C(n(n-1)/2,n) + C(n(n-1)/2,n-1) + ... + C(n(n-1)/2,0)
Question 38

Let G1 = (V,E1) and G2 = (V,E2) be connected graphs on the same vertex set V with more than two vertices. If G1 ∩ G2 = (V, E1 ∩ E2) is not a connected graph, then the graph G1 U G2 = (V, E1 U E2)

A
cannot have a cut vertex
B
must have a cycle
C
must have a cut-edge (bridge)
D
has chromatic number strictly greater than those of G1 and G2
       Engineering-Mathematics       Graph-Theory       GATE 2004
Question 38 Explanation: 
Lets try to take counter example for each of them,
(A)

False, since in G1∪G2 'C' is a cut vertex.
(B) True, for all conditions.
(C)

False. G1∪G2 has no bridge.
D)

False. G1∪G2, G1, G2 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

A
k and n
B
k – 1 and k + 1
C
k – 1 and n – 1
D
k + 1 and n – k
       Engineering-Mathematics       Graph-Theory       GATE 2003
Question 39 Explanation: 
While a vertex is removed from a graph then that can be itself be forms a new component. The minimum number of components is k-1.
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n-1) components.
Question 40

How many perfect matching are there in a complete graph of 6 vertices ?

A
15
B
24
C
30
D
60
       Engineering-Mathematics       Graph-Theory       GATE 2003
Question 40 Explanation: 
We have formula to find no. of perfect matching in complete graphs of 2n vertices,
(2n)!/n!×2n
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×23 = 15
Question 41

A graph G = (V,E) satisfies |E|≤ 3|V|-6. The min-degree of G is defined as . Therefore, min-degree of G cannot be

A
3
B
4
C
5
D
6
       Engineering-Mathematics       Graph-Theory       GATE 2003
Question 41 Explanation: 
The minimum degree of G = minv∈V {degree(v)}
|E| ≤ 3|v| - 6
Based on handshaking lemma, the minimum degree is (min×|v|)/2
⇒ (min×|v|)/2 ≤ 3|v| - 6
Checking the options lets take min=6
(6×|v|)/2 ≤ 3|v| - 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

A
2
B
3
C
4
D
n - 2[n/2] + 2
       Engineering-Mathematics       Graph-Theory       GATE 2002
Question 42 Explanation: 
We need 2 colours to colour even cycle and 3 colours to colour odd cycle.
Question 43

Maximum number of edges in a n-node undirected graph without self loops is

A
n2
B
n(n-1)/2
C
n-1
D
(n+1)(n)/2
       Engineering-Mathematics       Graph-Theory       GATE 2002
Question 43 Explanation: 
The set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n, 2)⋅ C(n, 2) = n(n-1)/2.
Question 44

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ...,vn} of n vertices?

A
n(n-1)/2
B
2n
C
n!
D
2n(n-1)/2
       Engineering-Mathematics       Graph-Theory       GATE 2001
Question 44 Explanation: 
With n vertices no. of possible edges = n C 2
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2(n C 2)
⇒ 2(n(n-1)/2)
Question 45

Let S be a set of n elements {1, 2, …., n} and G a graph with 2n 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 R1 and R2 is defined as (R1/R2)∪(R2/R1)
(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?

A
Theory Explanation is given below.
       Engineering-Mathematics       Graph-Theory       GATE 2000
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 men-cut 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 min-cut in the graph?

(c) Prove that if a connected undirected graph G with n vertices has a min-cut of cardinality K, then G has atleast (nk/2) edges.

A
Theory Explanation.
       Engineering-Mathematics       Graph-Theory       GATE 1999
Question 47

(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n-3)/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 = Rn.

A
Theory Explanation.
       Engineering-Mathematics       Graph-Theory       GATE 1998
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 

A
Theory Explanation.
       Engineering-Mathematics       Graph-Theory       GATE 1998
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

A
8
B
4
C
12
D
25
       Engineering-Mathematics       Graph-Theory       GATE 1997
Question 49 Explanation: 
From the description, it is clear that vertices are connected as follows:
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:

A
n - 1
B
n
C
n + 1
D
None of the above
       Engineering-Mathematics       Graph-Theory       GATE 1995
Question 50 Explanation: 
In a normal graph number of edges required for n vertices is n-1, and in cyclic graph it is n.
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.

A
Theory Explanation.
       Engineering-Mathematics       Graph-Theory       GATE 1995
Question 52

The number of distinct simple graphs with upto three nodes is

A
15
B
10
C
7
D
9
       Engineering-Mathematics       Graph-Theory       GATE 1994
Question 52 Explanation: 
Question 53

The number of edges in a regular graph of degree d and n vertices is _________.

A
d*n/2
       Engineering-Mathematics       Graph-Theory       GATE 1994
Question 53 Explanation: 
Sum of degree of vertices = 2 × no. of edges
d * n = 2 * |E|
∴ |E| = d*n/2
Question 54

Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour G is _____.

A
7
       Engineering-Mathematics       Graph-Theory       GATE 2020
Question 54 Explanation: 
In k3x4 there are two sets with sizes 3,4. (it is a complete bipartite graph).
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 ( K3x4 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 ________

A
3n - 6
       Engineering-Mathematics       Graph-Theory       GATE 1992
Question 55 Explanation: 
The maximum is 3(n - 8) for every n>2.
⇒ (3n - 2) = 3n - 6
Question 56

A non-planar graph with minimum number of vertices has

A
9 edges, 6 vertices
B
6 edges, 4 vertices
C
10 edges, 5 vertices
D
9 edges, 5 vertices
       Engineering-Mathematics       Graph-Theory       GATE 1992
Question 56 Explanation: 

The above graph with 5 vertices and 10 edges is non-planar.
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.

A
Theory Explanation.
       Engineering-Mathematics       Graph-Theory       GATE 1992
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 a2 = 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  
A
Theory Explanation.
       Engineering-Mathematics       Graph-Theory       GATE 1992
Question 59

The maximum number of possible edges in an undirected graph with a vertices and k components is ________.

A
(n-k)(n-k+1)/2
       Engineering-Mathematics       Graph-Theory       GATE 1991
Question 59 Explanation: 
N vertices and K components.
To get maximum, take one vertex each for each component, except last component.
Now, k-1 components have 1 vertex each and so on edges.
The last component has (n-(k-1)) vertices. So make the last component complete, i.e., it has n-(n-1)C2
= (n-k)(n-k+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,
A
It does not contain subgraphs homeomorphic to k5 and k3,3.
B
It does not contain subgraphs isomorphic to k5 or k3,3.
C
It does not contain a subgraph isomorphic to k5 or k3,3.
D
It does not contain a subgraph homeomorphic to k5 or k3,3.
       Engineering-Mathematics       Graph-Theory       GATE 1990
Question 60 Explanation: 
A graph is non-planar if and only if it contains a subgraph which is homomorphic to k5or k3,3. This is kuratowshi theorem.
Question 61

Which of the following graphs is/are planner?

A
Theory Explanation is given below.
       Engineering-Mathematics       Graph-Theory       GATE 1989
Question 61 Explanation: 
(i) G1 is K33 which is planar graph with the minimum number of edges.
→ Let us assume K33is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K33.
Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n-4.
Where m=9, n=6
⇒ 9 ≤ 12 - 4
⇒ 9 ≤ 8, which is to be false, then K33 is non-planar graph.
(ii) G2 is a planar graph. Because it can be redrawn like as below.

(iii) Let us assume G3 be a planar graph then it also be satisfy useful corollary.
Where m=9, n=6
then 9 ≤ 12-4
9 ≤ 8 is False
So, G3 is non-planar graph.
Answer: Only G2 is planar graph.
Question 62

What is the chromatic number of the following graph?

A
2
B
3
C
4
D
5
       Engineering-Mathematics       Graph-Theory       GATE 2008-IT
Question 62 Explanation: 
Chromatic number = 3
→ 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?

A
5
B
4
C
3
D
2
       Engineering-Mathematics       Graph-Theory       GATE 2008-IT
Question 63 Explanation: 
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
(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

A
Regular
B
Complete
C
Hamiltonian
D
Euler
       Engineering-Mathematics       Graph-Theory       GATE 2008-IT
Question 64 Explanation: 
Euler graph theory is a trail in a finite graph which visits every edge exactly once and which is a undirected graph.
→ 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

A
1/(2n-1)
B
1/n
C
2/n
D
3/n
       Engineering-Mathematics       Graph-Theory       GATE 2006-IT
Question 65 Explanation: 
For the given condition we can simply design a K-map and mark an edge between every two adjacent cells in K-map.
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 (n-1) 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?

A
There exists a cutset in G having all edges of maximum weight
B
There exists a cycle in G having all edges of maximum weight
C
Edge e cannot be contained in a cycle
D
All edges in G have the same weight
       Algorithms       Graph-Theory       GATE 2005-IT
Question 66 Explanation: 
(A) True, because if there is heaviest edge in MST, then there exist a cut with all edges with weight equal to heaviest edge.

(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

A
4
B
7
C
23
D
99
       Algorithms       Graph-Theory       GATE 2005-IT
Question 67 Explanation: 
Edge set consists of edges from i to j, using either
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?

A
n - 1
B
n
C
n + 1
D
2n - 1
       Engineering-Mathematics       Graph-Theory       GATE 2004-IT
Question 68 Explanation: 
Maximum number of edges in an acyclic undirected graph = No. of vertices - 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?

A
10
B
11
C
18
D
19
       Engineering-Mathematics       Graph-Theory       GATE 2004-IT
Question 69 Explanation: 
Let x = Total no. of vertices
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x - 9) * 3 = 27 * 2
24 + (x - 9) * 3 = 54
x = 19
Question 70
 In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______
A
11
       Engineering-Mathematics       Graph-Theory       GATE 2021 CS-Set-1
Question 70 Explanation: 

v - e + f = 2

v is number of vertices

e is number of edges

f is number of faces including bounded and unbounded

8-e+5=2

=> 13-2 =e

The number of edges  are =11

Question 71
Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:

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?
A
B
C
D
       Engineering-Mathematics       Graph-Theory       GATE 2021 CS-Set-1
Question 71 Explanation: 
Question 72
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
A
36
       Engineering-Mathematics       Graph-Theory       GATE 2022       Video-Explanation
Question 72 Explanation: 
We obtain maximum number of edges in a disconnected graph, with one isolated vertex and remaining completely connected.
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(n-1)/2 = 9*8/2 = 36
Question 73
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
A
A ^3
B
A^ 3 divided by 2
C
A ^3 divided by 3
D
A ^3 divided by 6
       Engineering-Mathematics       Graph-Theory       GATE 2022
Question 74
The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?
A
The chromatic number of the graph is 3.
B
The graph has a Hamiltonian path
C
The following graph is isomorphic to the Peterson graph.
D
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.)
       Engineering-Mathematics       Graph-Theory       GATE 2022
Question 74 Explanation: 
Chromatic number is 3.

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
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
A
The diagonal entries of A 2 are the degrees of the vertices of the graph.
B
If the graph is connected, then none of the entries of A^ n + 1 + I n can be zero.
C
If the sum of all the elements of A is at most 2( n- 1), then the graph must be acyclic.
D
If there is at least a 1 in each of A ’s rows and columns, then the graph must be Connected.
       Engineering-Mathematics       Graph-Theory       GATE 2022
Question 75 Explanation: 
IF A is adjacency matrix, then in the matrix A*A = A^2 we have
The entries aii show the number of 2-length 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 3-length paths between the nodes i and j.
In A^n-1 + I n, we will have at least n-1 length paths, so there is no possibility of zero entires
Question 76
The number of edges in a regular graph of degree d and n vertices is
A
maximum of n and d
B
n + d
C
nd
D
nd / 2
       Engineering-Mathematics       Graph-Theory       ISRO-2018
Question 76 Explanation: 
Sum of degree of vertices = 2 × no. of edges
d * n = 2 * |E|
∴ |E| = d*n/2
Question 77
Consider the graph shown in the figure below:

Which of the following is a valid strong component?
A
a, c, d
B
a, b, d
C
b, c, d
D
a, b, c
       Engineering-Mathematics       Graph-Theory       ISRO CS 2008
Question 77 Explanation: 
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.
The graph has (a, b, d) as a strongly connected component.
Question 78
If G is a graph with e edges and n vertices, the sum of the degrees of all vertices in G is
A
e
B
e/2
C
e2
D
2 e
       Engineering-Mathematics       Graph-Theory       ISRO CS 2009
Question 78 Explanation: 

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-

Σ degG(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
A given connected graph is a Euler Graph if and only if all vertices of are of
A
same degree
B
even degree
C
odd degree
D
different degree
       Engineering-Mathematics       Graph-Theory       ISRO-2016
Question 79 Explanation: 
A given connected graph is a Euler Graph if and only if all vertices of are of even 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 final edges of Z contribute one each to the degree of u. So the degree d(u) of u is also even.
Question 80
The maximum number of edges in a n-node undirected graph without self loops is
A
n2
B
n(n-1)/2
C
n-1
D
n(n+1)/2
       Engineering-Mathematics       Graph-Theory       ISRO-2016
Question 80 Explanation: 
The set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n,2)⋅C(n,2)=n(n-1)/2.
Question 81
A graph in which all nodes are of equal degree, is known as
A
Multigraph
B
Non regular graph
C
Regular graph
D
Complete graph
       Engineering-Mathematics       Graph-Theory       ISRO CS 2009
Question 81 Explanation: 

Question 82
In a graph G there is one and only one path between every pair of vertices then G is a
A
Path
B
Walk
C
Tree
D
Circuit
       Engineering-Mathematics       Graph-Theory       ISRO CS 2009
Question 82 Explanation: 
A graph is a tree if and only if there is exactly one path between every pair of its vertices.

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
A simple graph ( a graph without parallel edge or loops) with n vertices and k components can have at most
A
n edges
B
n-k edges
C
(n − k)(n − k + 1) edges
D
(n − k)(n − k + 1)/2 edges
       Engineering-Mathematics       Graph-Theory       ISRO CS 2009
Question 83 Explanation: 
Let G be a graph with k components. Let ni be the number of vertices in the ith component, where 1 ≤ i ≤ k. Then, the number of edges in G is equal to sum of the edges in each of its components.

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
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 down between
A
k and n
B
k-1 and k+1
C
k-1 and n-1
D
k+1 and n-k
       Engineering-Mathematics       Graph-Theory       ISRO CS 2009
Question 84 Explanation: 
→ While a vertex is removed from a graph then that can be itself be forms a new component. The minimum number of components is k-1.
→ If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n-1) components
Question 85
How many edges are there in a forest with v vertices and k components?
A
(v+1)−k
B
(v+1)/2 −k
C
v−k
D
v+k
       Engineering-Mathematics       Graph-theory       ISRO CS 2011
Question 85 Explanation: 
Method-1:
→ Suppose, if each vertex is a component, then k=v, then there will not be any edges among them. So, v-k= 0 edges.
Method-2:
→ 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
The number of edges in a ‘n’ vertex complete graph is ?
A
n * (n-1) / 2
B
n * (n+1) / 2
C
n2
D
n * (n+1)
       Engineering-Mathematics       Graph-theory       ISRO CS 2013
Question 86 Explanation: 
Complete graph is an undirected graph in which each vertex is connected to every vertex, other than itself. If there are ‘n’ vertices then total edges in a complete graph is n(n-1)/2
Question 87
Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
A
P only
B
Q only
C
Both P and Q
D
Neither P nor Q
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B CS 22-07-2017
Question 87 Explanation: 
Euler’s Theorem 3:
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
Consider the following graph L and find the bridges, if any.
A
No bridges
B
{d,e}
C
{c,d}
D
{c,d} and {c,f}
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B CS 22-07-2017
Question 88 Explanation: 
A bridge, ut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components.
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 isthmus-free 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
The following graph nas no Euler circuit because
A
It has 7 vertices
B
It is even-valent(all vertices have even valence)
C
It is not connected
D
It does not have a Euler circuit
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B CS 22-07-2017
Question 89 Explanation: 
An Eulerian trail or Euler walk in an undirected graph is a walk that uses each edge exactly once. If such a walk exists, the graph is called traversable or semi-eulerian.
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 edge-disjoint 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 edge-disjoint cycles and its nonzero-degree 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 edge-disjoint 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 (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph
Question 90
For the graph shown, which of the following paths is a Hamilton circuit?
A
ABCDCFDEFAEA
B
AEDCBAF
C
AEFDCBA
D
AFCDEBA
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B CS 22-07-2017
Question 90 Explanation: 
A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once. A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph.
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
If G is an undirected planar graph on n vertices with e edges then
A
e<=n
B
e<=2n
C
e<=en
D
None of the option
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B CS 22-07-2017
Question 91 Explanation: 
Euler's formula: states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and f is the number of faces (regions bounded by edges, including the outer, infinitely large region), then
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+(x-3)*3=30
Question 92
Choose the most appropriate definition of plane graph.
A
A simple graph which is isomorphic to hamiltonian graph
B
A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y
C
A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices
D
None of the option
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B CS 22-07-2017
Question 92 Explanation: 
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
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 K-coloring of an undirected graph G = (V, E) is a function

C: V ➝ {0, 1, ......, K-1} such that c(u)≠c(v) for every edge (u,v) ∈ E

Which of the following is not correct?

A
G has no cycles of odd length
B
G has cycle of odd length
C
G is 2-colorable
D
G is bipartite
       Engineering-Mathematics       Graph-Theory       UGC-NET CS 2018 DEC Paper-2
Question 93 Explanation: 
• A k-colouring of a graph G consists of k different colours and G is then called k-colourable.
• A cycle of length n ≥ 3 is 2-chromatic if n is even and 3-chromatic if n is odd.
• A graph is bi-colourable (2-chromatic) 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(n-1)(n-2) + 2

Choose the correct answer for the code given below:

Code:
A
(i) and (iii) only
B
(ii) and (iii) only
C
(iii) only
D
(ii) only
       Engineering-Mathematics       Graph-Theory       UGC-NET CS 2018 DEC Paper-2
Question 94 Explanation: 
Option-2 is correct.
→ Dirac's theorem on Hamiltonian cycles, the statement that an n-vertex 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 k-connected graphs, the result that for every set of k vertices in a k-vertex-connected graph there exists a cycle that passes through all the vertices in the set.
Question 95
The number of independent loops for a network with n nodes and b branch is
A
n-1
B
b-n
C
b-n+1
D
independent of "the number of nodes
       Engineering-Mathematics       Graph-Theory       NieLit STA 2016 March 2016
Question 95 Explanation: 
● A loop is a closed path in a circuit. Loop counts starting at a node passing through a set of nodes and returning to the starting node without passing through any node more than once.
● 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
The number of circuits in a tree with 'n' nodes is
A
Zero
B
One
C
n-1
D
n/2
       Engineering-Mathematics       Graph-Theory       NieLit STA 2016 March 2016
Question 96 Explanation: 
● A tree (e.g. a binary tree) has a root, branches (nodes), and leaf nodes.
● 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
A complete graph with "n" vertices is
A
2-chromatic
B
(n/2) chromatic
C
(n-1) chromatic
D
n-Chromatic
       Engineering-Mathematics       Graph-Theory       NieLit STA 2016 March 2016
Question 97 Explanation: 

Question 98
Minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same colour is
A
2
B
3
C
4
D
n-2⌈(n/2)⌉+2
       Engineering-Mathematics       Graph-Theory       NieLit STA 2016 March 2016
Question 98 Explanation: 
We need 3 colors to color a odd cycle and 2 colors to color an even cycle.
Question 99
How many ways are there to assign colours from the range {1, 2, . . . , r} to the vertices of the following graph so that adjacent vertices receive distinct colours?
A
r4
B
r4-4r3
C
r4-5r3+8r2-4r
D
r4-4r3+9r2-3r
E
r4-5r3+10r2-15r
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2018
Question 100
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:
A
3
B
4
C
5
D
6
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B CS 4-12-2016
Question 100 Explanation: 
v - e + f = 2
‘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
Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is
A
E
B
2E
C
V
D
2V
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B IT 22-07-2017
Question 101 Explanation: 
Theorem (Sum of Degrees of Vertices Theorem):
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
A path in graph G, which contains every vertex of G and only Once?
A
Euler circuit
B
Hamiltonian path
C
Euler Path
D
Hamiltonian Circuit
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B IT 22-07-2017
Question 102 Explanation: 
● Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle)
● 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
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph?
A
(a,b)(e,f)
B
(a,b),(a,c)
C
(c,d)(d,h)
D
(a,b)
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B IT 22-07-2017
Question 103 Explanation: 
● A bridge ,cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components.
● 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
Which of the following statements is/are TRUE?
S1: The existence of an Euler circuit implies that an euler path exists.
S2: The existence of an Euler path implies that an Euler circuit exists.
A
S1 is true
B
S2 is true
C
S1 and S2 both are true
D
S1 and S2 both are false
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B IT 22-07-2017
Question 104 Explanation: 
An Euler circuit in a graph G is a simple circuit containing every edge of G exactly once
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
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by 13 edges, then the number of regions is:
A
5
B
6
C
7
D
8
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B IT 22-07-2017
Question 105 Explanation: 
Use Euler's formula ,V−E+R=2
Where V is the number of vertices, E is the number of edges, and R is the number of regions.
R=2-V+E=2-8+13=7
Question 106
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
A
6
B
8
C
9
D
13
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B IT 22-07-2017
Question 106 Explanation: 
● Use Euler's formula ,V−E+R=2
● Where V is the number of vertices, E is the number of edges, and R is the number of regions.
● R=2-V+E=2-13+19=8
● We can also term region as face
Question 107
The number of diagonals that can be drawn by joining the vertices of an octagon is
A
28
B
48
C
20
D
None of the option
       Engineering-Mathematics       Graph-Theory       Nielit Scientist-B IT 22-07-2017
Question 107 Explanation: 
Octagon consists of the 8 vertices and we can draw 5 diagonals

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?

A
7
B
6
C
4
D
3
       Engineering-Mathematics       Graph-Theory       JT(IT) 2018 PART-B Computer Science
Question 108 Explanation: 
Euler's Formula for Planar Graphs:
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____

A
An odd number of edges
B
At least three edges
C
An even number of edges
D
A single edge
       Engineering-Mathematics       Graph-Theory       JT(IT) 2018 PART-B Computer Science
Question 109 Explanation: 
If every minimal cut has an even number of edges, then in particular the degree of each vertex is even. Since the graph is connected, that means it is Eulerian.
Question 110

A graph G is dual if and only if G is a ___

A
Euler graph
B
Regular graph
C
Complete graph
D
Planar graph
       Engineering-Mathematics       Graph-Theory       JT(IT) 2018 PART-B Computer Science
Question 110 Explanation: 
Definition Given a plane graph G, the dual graph G* is the plane graph whose vtcs are the faces of G.
→ 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 n-vertex simple connected graph, which does NOT contain any odd-length cycle?

A
N
B
N-1
C
2
D
3
       Engineering-Mathematics       Graph-Theory       JT(IT) 2018 PART-B Computer Science
Question 111 Explanation: 
→ If n ≥ 2 and there are no odd length cycles, Then it is bipartite graph.
→ 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
A
Neither (i) nor (ii)
B
Both (i) and (ii)
C
Only (ii)
D
Only (i)
       Engineering-Mathematics       Graph-Theory       JT(IT) 2018 PART-B Computer Science
Question 112 Explanation: 
True: Number of vertices of odd degree is always even.
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:

A
G and H are directed
B
G and H are isomorphic
C
G and H are homomorphic
D
G and H are not isomorphic
       Engineering-Mathematics       Graph-Theory       JT(IT) 2018 PART-B Computer Science
Question 113 Explanation: 
If G1 ≡ G2 then
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
The number of the edges in a regular graph of degree 'd' and 'n' vertices is____
A
Maximum of n,d
B
n+d
C
nd
D
nd/2
       Engineering-Mathematics       Graph-Theory       Nielit Scientific Assistance CS 15-10-2017
Question 114 Explanation: 
Sum of degree of vertices = 2*no. of edges
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
A spanning tree
B
A connected graph
C
A directed graph
D
A biconnected component
       Engineering-Mathematics       Graph-Theory       JT(IT) 2016 PART-B Computer Science
Question 115 Explanation: 
Given a connected graph G, a connected subgraph that is both a tree and contains all the vertices of G is called a spanning tree for G.
Question 116
Consider a Hamiltonian Graph G with no loops or parallel edges and with |V(G)| = n ≥ 3. Then which of the following is true ?
A
deg(v) ≥n/2 for each vertex v.
B
|E(G)| ≥1/2(n – 1) (n – 2) + 2
C
deg (v) + deg(w) ≥ n whenever v and w are not connected by an edge
D
All of the above
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2017 Jan -paper-2
Question 116 Explanation: 
With the help of dirac’s theorem, we can prove above three statements.
Question 117
Given the following graphs:

Which of the following is correct?
A
G​ 1​ contains Euler circuit and G​ 2​ does not contain Euler circuit.
B
G​ 1​ does not contain Euler circuit and G​ 2​ contains Euler circuit.
C
Both G​ 1​ and G​ 2​ do not contain Euler circuit.
D
Both G​ 1​ and G​ 2​ contain Euler circuit.
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2016 Aug- paper-2
Question 117 Explanation: 

Step-1: G1 have odd number of vertices. So, it is not euler circuit.
Step-2: G2 also have odd number of vertices. So, it not euler circuit.
Question 118
The number of different spanning trees in complete graph, K​ 4​ and bipartite graph, K​ 2,2​ have ______ and _______ respectively.
A
14, 14
B
16, 14
C
16, 4
D
14, 4
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2016 July- paper-2
Question 118 Explanation: 
Step-1: Given complete graph K​ 4​ .To find total number of spanning tree in complete graph using standard formula is n​ (n-2) Here, n=4
=n​ (n-2)
= 4​ 2
=16
Step-2: Given Bipartite graph K​ 2,2​ . To find number of spanning tree in a bipartite graph K​ m,n​ having standard formula is m​ (n-1)​ * n​ (m-1)​ .
m=2 and n=2
= 2​ (2-1)​ * 2​ (2-1)
= 2 * 2
= 4
Question 119
A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. How many cliques are there in the graph shown below?

A
2
B
4
C
5
D
6
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2016 July- paper-2
Question 119 Explanation: 
Definition of clique is already given in question.
Definition: A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph.
Step-1: b,c,e,f is complete graph.

Step-2: ‘a’ is not connected to ‘e’ and ‘b’ is not connected to ‘d’. So, it is not complete graph.
Question 120
Which of the following statement(s) is/are false ?
(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
(a) only
B
(b) and (c)
C
(c) only
D
(d) only
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2015 Dec- paper-2
Question 120 Explanation: 
(a)TRUE: A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
(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:
A
(v​ 1​ , v​ 4​ , v​ 6​ ); (v​ 2​ , v3​ , v​ 5​ , v​ 7​ , v​ 8​ )
B
(v​ 1​ , v​ 7​ , v​ 8​ ); (v​ 2​ , v​ 3​ , v​ 5​ , v​ 6​ )
C
(v​ 1​ , v​ 4​ , v​ 6​ , v​ 7​ ); (v​ 2​ , v​ 3​ , v​ 5​ , v​ 8​ )
D
(v​ 1​ , v​ 4​ , v​ 6​ , v​ 7​ , v​ 8​ ); (v​ 2​ , v​ 3​ , v​ 5​ )
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2015 Dec- paper-2
Question 121 Explanation: 
A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
→ 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.

Option-B FALSE because V​ 5​ , V​ 6​ and V​ 2​ are adjacent. So, it not not bipartite graph.

Option-C TRUE because it follows properties of bipartied and no two colours are adjacent.

Option-D FALSE because because V​ 4​ , V​ 6​ and V​ 8​ are adjacent. So, it not not bipartite graph.
Question 122
A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2,....n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful?
(a)
(b)
(c)
A
(a) and (b)
B
(b) and (c)
C
(a) and (c)
D
(a), (b) and (c)
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2015 Dec- paper-2
Question 122 Explanation: 
Above all graphs are graceful.

Question 123
Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is true with respect to this Graph (G) ?
(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
(a) and (b)
B
(b) and (c)
C
(a) and (c)
D
(a), (b) and (c)
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2015 Jun- paper-2
Question 123 Explanation: 
→ According to Dirac's theorem on Hamiltonian cycles, the statement that an n-vertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle.
→ 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 edge-disjoint Hamiltonian cycles in G cannot exceed (n − 1)/2. When n is odd, we show there are (n − 1)/2 edge-disjoint Hamiltonian cycles.
So the statement(b) is false and statement a and c are true.
Question 124
The following lists are the degrees of all the vertices of a graph :
(i) 1, 2, 3, 4, 5
(ii) 3, 4, 5, 6, 7
(iii) 1, 4, 5, 8, 6
(iv) 3, 4, 5, 6
then
A
(i) and (ii)
B
(iii) and (iv)
C
(iii) and (ii)
D
(ii) and (iv)
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2004 Dec-Paper-2
Question 124 Explanation: 
Every graph is following basic 2 properties:
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 property-1.
= 1+2+3+4+5
= 15 is odd number.
Statement-(ii) is violating property-1.
= 3+4+5+6+7
= 25 is odd number.
Statement-(iii) is violating property-1.
= 1+4+5+8+6
= 24 is even number
Statement-(iv) is violating property-1
= 3+4+5+6
= 18 is even number
Question 125
T is a graph with n vertices. T is connected and has exactly n-1 edges, then :
A
T is a tree
B
T contains no cycles
C
Every pairs of vertices in T is connected by exactly one path
D
All of these
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2005 Dec-Paper-2
Question 125 Explanation: 
This is little bit tricky question.
Step-1:
n= number of vertices
n-1 = number of edges
Example: n=5 vertices and n-1=4 edges

Step-2: 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
The number of edges in a complete graph with N vertices is equal to :
A
N (N−1)
B
2N−1
C
N−1
D
N(N−1)/2
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2006 Dec-paper-2
Question 126 Explanation: 
N =5
Question 127
For a complete graph with N vertices, the total number of spanning trees is given by :
A
2N-1
B
N​ N-1
C
N​ N-2
D
2N+1
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2006 June-Paper-2
Question 127 Explanation: 
If a graph is complete, total number of spanning trees are N​ N-2
Example:

Formula to find total number of spanning trees are N​ N-2
=5​ 5-2
=5​ 3
=125
Question 128
A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph ?
A
5
B
n-3
C
20
D
11
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2014 Dec-Paper-2
Question 128 Explanation: 
Method-1:
Here, they are clearly mentioned that “certain tree”
The tree contain maximum n-1 edges. Here, ‘n’ is number of vertices.
→ According to the handshaking lemma “sum of degrees of all vertices=2|e|”.
→ 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)
Step-1: (2*4)+(1*3)+(1*2)+(X*1)
=2(X+4-1) [Note: ‘X’ value is not given ]
X=7
Step-2: To find total number of vertices, we are adding X+4 because they already given 4 vertices.
=X+4
=7+4
=11
Method-2:
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
Consider the Graph shown below :

This graph is a __________.
A
Complete Graph
B
Bipartite Graph
C
Hamiltonian Graph
D
All of the above
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2014 Dec-Paper-2
Question 129 Explanation: 
Option-A: It is not complete graph because it won’t have n(n-1)/2 edges.
Option-B: It is not Bipartite Graph because it takes more than 2 colours. Bipartite Graph have exactly 2 colours.
Option-C: Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once.

Hence, Option-C is correct answer.
Question 130
Consider the following statements related to AND-OR Search algorithm.
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 non-deterministic environment.
Which one of the following is true referencing the above statements?
Choose the correct answer from the code given below:
A
S1- False, S2- True, S3- True
B
S1- True, S2- True, S3- True
C
S1- False, S2- True, S3- False
D
S1- True, S2- True, S3- False
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2018-DEC Paper-2
Question 130 Explanation: 
● An and–or tree is a graphical representation of the reduction of problems (or goals) to conjunctions and disjunctions of subproblems (or subgoals).
● A solution in an AND-OR tree is a sub tree whose leaves are included in the goal set
Question 131
The K-coloring of an undirected graph G=(V,E) is a function C: V➝{0,1,......,K-1} such that c(u)≠c(v) for every edge (u,v) ∈ E Which of the following is not correct?
A
G has no cycles of odd length
B
G has cycle of odd length
C
G is 2-colorable
D
G is bipartite
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2018-DEC Paper-2
Question 131 Explanation: 
● A k-colouring of a graph G consists of k different colours and G is then called k-colourable.
● A cycle of length n ≥ 3 is 2-chromatic if n is even and 3-chromatic if n is odd.
● A graph is bi-colourable (2-chromatic) if and only if it has no odd cycles.
● A nonempty graph G is bicolourable if and only if G is bipartite
Question 132
​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 (n − 1 )(n − 2 ) + 2
A
(i) and (iii) only
B
(ii) and (iii) only
C
(iii) only
D
(ii) only
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2018-DEC Paper-2
Question 132 Explanation: 
→ Dirac's theorem on Hamiltonian cycles, the statement that an n-vertex 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 k-connected graphs, the result that for every set of k vertices in a k-vertex-connected graph there exists a cycle that passes through all the vertices in the set
Question 133
Consider the graph given below as :

Which one of the following graph is isomorphic to the above graph ?
A
B
C
D
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2014 June-paper-2
Question 133 Explanation: 
If two graphs are isomorphic, they must have:
→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.
Option-A: Vertex v5 having degree 4. So, it is not isomorphic graph.
Option-B: Vertex v6 having degree 4. So, it is not isomorphic graph.
Option-C: Every vertex having degree 3 and total number of edges and vertices are 12 and 8.
So, it is isomorphic.
Option-D: Vertex v6 having degree 4. So, it is not isomorphic graph.
Question 134
Consider a complete bipartite graph km,n. For which values of m and n does this, complete graph have a Hamilton circuit
A
m = 3, n = 2
B
m = 2, n = 3
C
m = n ≥ 2
D
m = n ≥ 3
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2014 June-paper-2
Question 134 Explanation: 
Complete graph have a Hamilton circuit m=n ≥ 2. If G is connected simple graph with n vertices where n≥3, then G has a Hamilton circuit if the degree of each vertex is at least n/2.
Question 135
Match List1 with List 2 and choose the correct answer from the code given below :

Where V and E are the number of vertices and edges in graph respectively.
A
(a)-(i), (b)-(iii), (c)-(iv), (d)-(ii)
B
(a)-(i), (b)-(iii), (c)-(ii), (d)-(iv)
C
(a)-(iii), (b)-(i), (c)-(ii), (d)-(iv)
D
(a)-(iii), (b)-(i), (c)-(iv), (d)-(ii)
       Regular-Expression       Graph-Theory       UGC NET CS 2018-DEC Paper-2
Question 135 Explanation: 
→ Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph and time complexity is O(V​ 2​ )
→ Kruskal's algorithm is a minimum-spanning-tree 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
Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is
A
2451
B
4950
C
4851
D
9900
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2013 Sep-paper-2
Question 136 Explanation: 
Given data,
-- Undirected graph G with 100 nodes.
-- Maximum number of edges to be included in G so that the graph is not connected is ?
Step-1: As per the above description, it is simple undirected graph.
For simple graph using formula standard formula is ((n-1)*(n-2))/2
Step-2: Here, n=100
n-1=99
n-2=98
=((n-1)(n-2))/2
= (99*98)/2
= 4851
Note: The simple graph won’t have parallel edges and self loops.
Question 137
Consider the following statements :
(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 ?
A
(i) & (iii)
B
(ii) & (iii)
C
(i) & (ii)
D
All of the above
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2013 Sep-paper-2
Question 137 Explanation: 

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
A simple graph G with n-vertices is connected if the graph has
A
(n – 1) (n – 2)/2 edges
B
more than (n – 1) (n – 2)/2 edges
C
less than (n – 1) (n – 2)/2 edges
D
Σki=1 C(ni, 2) edges
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2013 Sep-paper-2
Question 138 Explanation: 
The simple graph won’t have parallel edges and self loops.
Simple graph properties:
→If a graph is connected then e≥n-1.
→If a graph has more than e>((n-1)(n-2)) / 2 then it is connected.
→The n vertex graph with the maximal number of edges that is still disconnected is a Kn-1
→A complete graph Kn-1 with n-1 vertices ((n-1)(n-2)) / 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
A graph is non-planar if and only if it contains a subgraph homomorphic to
A
K3, 2 or K5
B
K3, 3 and K6
C
K3, 3 or K5
D
K2, 3 and K5
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2013 Dec-paper-2
Question 139 Explanation: 
A graph is non-planar if and only if it contains a subgraph which is homomorphic to k5 or k3,3. This is kuratowshi theorem.
Question 140
The number of colours required to properly colour the vertices of every planar graph is
A
2
B
3
C
4
D
5
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2012 June-Paper2
Question 140 Explanation: 
→ The 4-colour theorem of the planar graph describes that any planar can at most be colored with 4 colors.
→ The sufficient number of colors in worst case is 4 colors for any planar graph.
Question 141
Maximum number of edges in a n-Node undirected graph without self loop is
A
n2
B
n(n-1)
C
n(n+1)
D
n(n-1)/2
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2011 Dec-Paper-2
Question 141 Explanation: 
The set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n,2)⋅C(n,2) = n(n-1)/2
Question 142
Cyclometric complexity of a flow graph G with n vertices and e edges is
A
V(G) = e+n–2
B
V(G) = e–n+2
C
V(G) = e+n+2
D
V(G) = e–n–2
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2013 June-paper-2
Question 142 Explanation: 
Cyclomatic complexity uses 3 formulas:
1. The number of regions corresponds to the cyclomatic complexity
2. V(G),Flow graph is defined as V(G)=E-N+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
How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components ?
A
M+N–C
B
M–N–C
C
M–N+C
D
M+N+C
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2013 June-paper-2
Question 143 Explanation: 
→ Spanning forest is nothing but a set of spanning trees, one for each connected component in the graph
→ 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 M-N+C=8-9+3=2
So option C is correct.
Question 144
An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices are
A
all of even degree
B
all of odd degree
C
of any degree
D
even in number
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2010 Dec-Paper-2
Question 144 Explanation: 
→ An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices all of even degree.
→ Eulerian circuit (or) Euler tour in an undirected graph is a cycle that uses each edge exactly once.
Question 145
The minimum number of edges in a connected graph with ‘n’ vertices is equal to
A
n(n – 1)
B
n(n–1)/2
C
n2
D
n – 1
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2010 Dec-Paper-2
Question 145 Explanation: 

Question 146
S1 : I teach algorithms and maths.
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 edges-to represent the associations/relationships amongst the entities/actors as expressed in the sentences S1 to S5 above ?
A
2
B
3
C
4
D
None of these
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2010 June-Paper-2
Question 147
The complete graph with four vertices has k edges where k is :
A
3
B
4
C
5
D
6
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2009-June-Paper-2
Question 147 Explanation: 
To find number of edges in complete graph using standard formula is n(n-1)/2

n=4
= 4(4-3)/2
= (4*3)/2
= 12/2
= 6
Question 148
Which two of the following are equivalent for an undirected graph G ?
(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 (n-1) edges
(iv) G has n edges
A
(i) and (ii)
B
(i) and (iii)
C
(i) and (iv)
D
(ii) and (iii)
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2009-June-Paper-2
Question 148 Explanation: 
Option-A: FALSE because undirected graph will be cycle also.
Option-B: TRUE because there is at least one path between any two distinct vertices of G. otherwise we are no calling as undirected graph.
Option-C: TRUE. If G contains no cycles and has (n-1) edges.
Option-D: FALSE
Question 149
The number of edges in a complete graph of n vertices is
A
n
B
n(n – 1)/2
C
n(n + 1)/2
D
n2/2
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2009 Dec-Paper-2
Question 149 Explanation: 
Complete graph is an undirected graph in which each vertex is connected to every vertex, other than itself. If there are ‘n’ vertices then total edges in a complete graph is n(n-1)/2.
Ex:

n=5 and complete graph
Using formula to find number of edges is n(n-1)/2
=5*(5-1)/2
=(5*4)/2
=10
Question 150
The graph K3,4 has :
A
3 edges
B
4 edges
C
7 edges
D
12 edges
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2008 Dec-Paper-2
Question 150 Explanation: 
The graph K3,4 means it complete bipartite graph with m=4 and n=3
Total number of vertices= n + m
Total number of edges= m*n
Example:
Question 151
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex?
A
3
B
0
C
5
D
4
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 151 Explanation: 
The number of odd degree vertices in any graph is even. Since we already have four vertices of odd degree, the degree of the last vertex cannot be 3 or 5. It cannot be 0 either, since there is one vertex with degree 7, which means that it is a neighbour to all the other vertices, which implies that there is no isolated vertex in the graph. Thus the only possible degree of the last vertex is 4.
Question 152
A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 152 Explanation: 
Let V be the set of all vertices. A path between u to v through w is formed by a subset V ' of V \ {u, v, w} and forming a permutation of V' ∪ {w}. Now for each i ≤ 7, there (7 i) are subsets V' of size i, and (i + 1)! permutations of V' ∪ {w}.
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
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least two vertices with the same degree.
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE (M.Sc. / Ph.D. Programme in Computer Science)15 May 2013
Question 153 Explanation: 
Let n be the number of vertices in a simple graph. The maximum possible degree is n − 1. Let us observe that it is not possible for there to simultaneously be two vertices u and v such that u is of degree 0 and v is of degree n − 1 (since in that case u would have no neighbours, while every vertex other than v – in particular, u – is v’s neighbour, which is a contradiction). Therefore there are only n − 1 possible degrees for the n vertices, which means that two vertices should have the same degree, by the pigeonhole principle.
Question 154
Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not an endpoint of any green coloured edge. If a graph G does not satisfy this property, which of the following statements about G are valid?
A
There is a red coloured edge.
B
Any vertex that is the endpoint of a red coloured edge is also the endpoint of a green coloured edge.
C
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.
D
(a) and (c).
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 154 Explanation: 
Let r(x) denote the fact that the vertex x is the endpoint of a red coloured edge, and similarly for b(x) and g(x). The given property P can be expressed by the following formula.
∀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
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable. The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:
A
Find a spanning tree with minimum number of edges.
B
Find a minimal colouring.
C
Find a minimum size vertex cover.
D
Find a maximum size independent set.
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 155 Explanation: 
If we represent each slot by a colour, then a colouring of the graph is an assignment of courses to slots, such that courses with overlapping audiences are in different slots. A minimal colouring minimizes the number of slots needed.
Question 156
An undirected graph has 10 vertices labelled {1, 2, . . . , 10} and 37 edges. Vertices 1, 3, 5, 7, 9 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 10?
A
5
B
6
C
7
D
8
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 156 Explanation: 
The sum of the degrees is twice the number of edges, which is 74 in this case. The degrees of the vertices {1, 2, . . . , 9} add up to 68. Hence 6 is the correct answer.
Question 157
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at intersections with traffic lights so that any segment of road can be reached by at least one ambulance that does not have to pass through a traffic light to reach the scene of the accident. If we model the road network as a graph, where intersections with traffic lights are vertices and edges represent road segments between traffic lights, the graph theoretic question to be answered is:
A
Find a spanning tree with minimum number of edges.
B
Find a spanning tree with minimum cost.
C
Find a minimal colouring.
D
Find a minimum size vertex cover.
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 157 Explanation: 
Each ambulance “covers” the adjacent roads, and all roads are covered in this way.
Question 158
Let G be an arbitrary graph on n vertices with 4n − 16 edges. Consider the following statements: I There is a vertex of degree smaller than 8 in G. II There is a vertex such that there are less than 16 vertices at distance exactly 2 from it. Which of the following is true:
A
I only
B
II only
C
Both I and II
D
Neither I nor II
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 158 Explanation: 
By the Pigeonhole Principle, there is a vertex of degree < 8.
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 non-neighbours 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
An undirected graph is connected if, for any two vertices {u, v} of the graph, there is a path in the graph starting at u and ending at v. A tree is a connected, undirected graph that contains no cycle. (a) A leaf in a tree is a vertex that has degree 1. Prove that if G is a tree with at least two vertices then G contains at least two leaves. (b) A bipartite graph is one in which the vertex set V can be partitioned into two disjoint sets V 1 and V 2 so that for every edge {u, v}, u and v lie in different partitions—that is, u ∈ V 1 and v ∈ V 2 or vice versa. Prove that if G is a tree with at least two vertices, then G is bipartite.
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 159 Explanation: 
(a) Consider a maximal path ρ = v 0 v 1 . . . v k in the tree. If v0 is not a leaf, then it has a neighbour v not equal to v 1 , and the path ρ can be extended to a longer one vρ since there are no cycles. This contradicts the fact that ρ is maximal, thereby showing that v 0 is a leaf. A similar argument shows that v k is also a leaf.
(b) If we root the tree at any node, we can colour the tree level by level by alternating two colours. This 2-colouring gives us the partition of the vertex set
Question 160
The number of edges in a complete graph with ‘n’ vertices is equal to :
A
n(n-1)
B
n(n-1)/2
C
n2
D
2n-1
       Engineering-Mathematics       Graph-Theory       UGC NET CS 2007-Dec-Paper-2
Question 160 Explanation: 
Complete graph is an undirected graph in which each vertex is connected to every vertex, other than itself. If there are ‘n’ vertices then total edges in a complete graph is n(n-1)/2.

Question 161
A dodecahedron is a regular solid with 12 faces, each face being a regular pentagon. How many edges are there? And how many vertices?
A
60 edges and 20 vertices.
B
30 edges and 20 vertices.
C
60 edges and 50 vertices.
D
30 edges and 50 vertices.
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)
Question 161 Explanation: 
Each face has five edges, and there are 12 faces. But each edge is shared between two faces. Thus the number of edges is (12 × 5)/2 = 30. The number of vertices is given by Euler’s formula to be |E| − |F | + 2 = 30 − 12 + 2 = 20.
Question 162
ScamTel has won a state government contract to connect 17 cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected—there is a path from each city to every other city. The contract requires the network to remain connected if any single link fails. What is the minimum number of links that ScamTel needs to set up?
A
34
B
32
C
17
D
16
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)
Question 162 Explanation: 
If we connect the cities in a loop with 17 links, then even if any single link fails, we can connect the cities by traversing the loop the other way. If we only had 16 links connecting 16 cities, that would constitute a tree which would have only a single path between any pair of cities (and thus get disconnected by a single link failure).
Question 163
A simple path (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The length of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let G be an undirected graph with minimum degree k ≥ 2. (a) Show that G contains a simple path of length at least k. (b) Show that G contains a simple cycle of length at least k + 1.
A
Explanation
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)
Question 163 Explanation: 
Build a path in the graph as follows:
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
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:

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.
A
Explanation
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)
Question 164 Explanation: 
Assign a distinct natural number N (v) to each vertex v of the graph. For an edge between v and w, choose the direction v → w provided N (v) < N (w). It is easy to prove that if there is a directed path from v to w in this scheme, then N (v) < N (w). Suppose there is a directed cycle involving v. This means that there is a directed path from v to itself, whence N (v) < N (v), which is a contradiction.
Question 165
Let G = (V, E) be an undirected simple graph, and s be a designated vertex in G. For each v ∈ V , let d(v) be the length of a shortest path between s and v. For an edge (u, v) in G, what can not be the value of d(u) − d(v)?
A
2
B
-1
C
0
D
1
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 165 Explanation: 
Note that d(u) ⩽ d(v) + 1
Question 166
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each individual has the skills to take part in a subset of the events. However, the same individual cannot be part of the team for two different events because of a possible clash in timings. Your aim is to create teams to take part in as many events as possible.
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:
A
Find a maximum length simple cycle
B
Find a maximum size independent set
C
Find a maximum matching
D
Find a maximal connected component
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 167
Let G be a simple graph on n vertices.
(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.
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 167 Explanation: 
Question 168
Suppose that a connected planar graph has six vertices, each of degrees four. Into how many regions is the plane divided by a planar representation of this graph?
A
6
B
8
C
12
D
10
       Engineering-Mathematics       Graph-Theory       UGC NET June-2019 CS Paper-2
Question 168 Explanation: 
We apply Euler’s formula where r = e−v + 2.
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
For which values of m and n does the complete bipartite graph km,n have a Hamilton circuit?
A
m≠n, m, n≥2
B
m≠n, m, n≥3
C
m=n, m, n≥2
D
m=2, m, n≥3
       Engineering-Mathematics       Graph-Theory       UGC NET June-2019 CS Paper-2
Question 169 Explanation: 
let G=(A|B,E) be a bipartite graph. Let G be Hamiltanion.
Then |A|=|B|
That is, there is the same number of vertices in A as there are in B.
Question 170
In an undirected graph G with n vertices, vertex 1 has degree 1, while each vertex 2, . . ., n − 1 has degree 10 and the degree of vertex n is unknown. Which of the following statements must be TRUE of the graph G?
A
There is a path from vertex 1 to vertex n
B
There is a path from vertex 1 to each vertex 2, . . ., n − 1
C
Vertex n has degree 1
D
The diameter of the graph is at most n/10
E
All of the above choices must be TRUE
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2018
Question 171
A tree has 2n vertices of degree 1, 3n vertices of degree 2, n vertices of degree 3. Determine the number of vertices and edges in tree.
A
12.11
B
11.12
C
10.11
D
9.10
       Engineering-Mathematics       Graph-Theory       UGC-NET DEC-2019 Part-2
Question 172
A clique in an undirected graph G = (V, E) is a subset V’ ⊆ V of vertices, such that
A
If (u, v) ∈ E then u ∈ V’ and v ∈ V’
B
If (u, v) ∈ E then u ∈ V’ or v ∈ V’
C
Each pair of vertices in V’ is connected by an edge
D
All pairs of vertices in V’ are not connected by an edge
       Engineering-Mathematics       Graph-Theory       UGC-NET DEC-2019 Part-2
Question 172 Explanation: 
A clique in an undirected graph G = (V, E) is a subset V’ ⊆ V of vertices, such that each pair of vertices in V’ is connected by an edge
Question 173
Consider a random graph G on n vertices where for each pair of vertices u, v, there is an edge (u, v) with probability p ∈ [0, 1]. What is the expected number of cycles of length 3 in this graph?
A
B
C
D
None of the above
       Engineering-Mathematics       Graph-Theory       CMI PHD 2022
Question 173 Explanation: 
Question 174

Let k2,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?


A
2
B
3
C
4
D
1
       Engineering-Mathematics       Graph-Theory       CIL Part - B
Question 175
Maximum number of edges in a simple graph with ‘n’ vertices and ‘k’ components is:
A
[(n-2)(n-1)/2]+1
B
[(n-k)(n-k+1)]/2
C
n2
D
[(n)(n-1)]/2
       Engineering-Mathematics       Graph-Theory       CIL Part - B
Question 175 Explanation: 
A simple graph with n vertices and k components can have at most have (n-k)(n-k+1)/2 edges.
Question 176
If a connected graph G does not contain any vertex whose removal disconnects the rest of the graph, then G is called:
A
Biconnected graph
B
Separable graph
C
Forest
D
Diagraph
       Engineering-Mathematics       Graph-Theory       CIL Part - B
Question 176 Explanation: 
A biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.
Question 177
The minimum number of edges of a graph containing n vertices and c connected components is
A
n-c
B
c
C
c(n-1)
D
n/c
       Engineering-Mathematics       Graph-Theory       APPSC-2016-DL-CS
Question 177 Explanation: 
We have to find a minimum no. of edges. So for c connected components let's assume c-1 independent vertices which are also c-1 components and remaining 1 component will contain n-(c-1) vertices or n-c+1 vertices. So for minimum no. of edges will be no. of vertices in the single component (which contains n-c+1 vertices) -1, which is (n-c+1)-1 = n-c
Question 178

For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is

A
2n
B
(2n-1)/2
C
2e
D
e2/2
       Engineering-Mathematics       Graph-Theory       APPSC-2016-DL-CA
Question 178 Explanation: 
sum of the degree of each vertex = 2 * no. of edges
Question 179

The complete graph Kn has _______ different spanning trees.

A
nn-2
B
n×n
C
nn
D
n2
       Engineering-Mathematics       Graph-Theory       APPSC-2016-DL-CA
Question 179 Explanation: 
Formula for the complete graph kn has nn-2 different spanning trees.
Question 180

Which of the following is not a type of graph?

A
Euler
B
Hamiltonian
C
Tree
D
Path
       Engineering-Mathematics       Graph-Theory       APPSC-2016-DL-CA
Question 180 Explanation: 
Path is not a type of graph.
Question 181

If G is an undirected planar graph on n vertices with e edges then?

A
e<=n
B
e<=2n
C
e<=3n
D
None of the given options
       Engineering-Mathematics       Graph-Theory       APPSC-2016-DL-CA
Question 181 Explanation: 
for planar graphs, 3r <= 2e and n - e + r = 2
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

A
Start vertex
B
Middle point
C
Terminal vertex
D
Articulation point/Cut vertex
       Engineering-Mathematics       Graph-Theory       CIL 2020
Question 182 Explanation: 
An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph).
Question 183

A vertex of how many degree is isolated?

A
0
B
1
C
2
D
3
       Engineering-Mathematics       Graph-Theory       APPSC-2012-DL CA
Question 183 Explanation: 
A vertex is isolated if and only if it is not connected to any other vertices. Means a vertex of degree zero is said to be isolated.
Question 184

A closed path with no other repeated vertices than the starting and ending vertices is known as

A
Steiner tree
B
Cycle
C
Complement graph
D
Spanning tree
       Engineering-Mathematics       Graph-Theory       APPSC-2012-DL CA
Question 184 Explanation: 
A closed path with no other repeated vertices than the starting and ending vertices is called cycle.
Question 185
Which of the following statements is false?
A
A tree contains a cycle
B
Every tree is a graph
C
A tree with N nodes contain N-1 edges
D
All the above
       Engineering-Mathematics       Graph-Theory       APPSC-2012-DL-CS
Question 185 Explanation: 
A tree does not contain a cycle. A tree with n vertices contains n-1 edges. And every tree is a graph.
Question 186
T is a graph with n vertices. T is connected and has exactly n – 1 edges. Then
A
T is a tree
B
T contains no cycles
C
Every pair of vertices in T is connected by exactly one path
D
Addition of a new edge will create a cycle
       Engineering-Mathematics       Graph-Theory       TNPSC-2012-Polytechnic-CS
Question 186 Explanation: 
Any graph with n vertices and n-1 edges which is connected will definitely be a tree.
Question 187
What is true for the complete bipartite graphs k (3, 3) and k (2, 4) ?
A
Both are planar
B
Neither is planar
C
Both are isomorphic
D
None of these
       Engineering-Mathematics       Graph-Theory       TNPSC-2012-Polytechnic-CS
Question 187 Explanation: 
The graph k(1,n) is planar for all n.
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 non-planar by kuratowski’s theorem.
Hence K(3,3) is not planar where as k(2,4) is planar.
Question 188
Between any two vertices, there exists a path, then the graph is said to be
A
Strongly Connected
B
Connected
C
Weakly Connected
D
All the above
       Engineering-Mathematics       Graph-Theory       TNPSC-2017-Polytechnic-CS
Question 188 Explanation: 
If between any two vertices there exists a path then the graph is said to be strongly connected and every strongly connected graph is weakly connected(vice versa need not be true). And moreover it is connected graph.
Question 189
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node A?
A
D
B
H
C
I
D
M
       Engineering-Mathematics       Graph-Theory       CMI 2019
Question 189 Explanation: 
The predecessor of A is the rightmost node in the left subtree of A.
Question 190
There is a party of n people. Each attendee has at most r friends in the party. The friend circle of a person includes the person and all her friends. You are required to pick some people for a party game, with the restriction that at most one person is picked from each friend circle. Show that you can pick n/(r2+1) people for the game.
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CMI 2019
Question 190 Explanation: 
Consider an undirected graph where each vertex represents a person and there is an edge between two vertices if the corresponding people are friends. Suppose we pick two people who are at distance <= 2 from each other. Then they are either friends or share a friend, so they have overlapping friend circles (which could be the same circle). Thus we should ensure that no two people we pick for the party game are at distance <= 2 from each other.
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 r2 + 1 vertices, of which we have picked one. We continue similarly for the remaining vertices to pick at least n/(r2+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
Consider the assertion: Any connected undirected graph G with at least two vertices contains a vertex v such that deleting v from G results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CMI 2019
Question 191 Explanation: 
The assertion is true. Consider a longest path v0v1 ... vt in G. The vertex v0 can play the role of the vertex v in the question. Suppose deleting v0 results in a graph with two or more components. All of v0v1 ... vt will be together in one component. There is a vertex u in a deferent component of G-v0 such that uv0v1 ... vt is a longer path in G, a contradiction.
Question 192
A graph is d-regular if every vertex has degree d. For a d-regular graph on n vertices, which of the following must be TRUE?
A
d divides n
B
Both d and n are even
C
Both d and n are odd
D
At least one of d and n is odd
E
At least one of d and n is even
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2019
Question 193
Let G = (V, E) be a directed graph with n ( >= 2) vertices, including a special vertex r. Each edge e ∈ E has a strictly positive edge weight w(e).
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?
A
B
C
H has exactly n − 1 edges
D
H is acyclic
E
w is less than the weight of the minimum weight directed Hamiltonian cycle in G, whenever G has a directed Hamiltonian cycle
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2019
Question 194
Consider directed graphs on n labelled vertices { 1, 2, . . . , n } where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many such graphs have exactly two cycles?
A
a
B
b
C
c
D
d
E
None of the above
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2019
Question 195
A
39
B
63
C
3*28
D
27
E
24
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2017
Question 196
A vertex colouring of a graph G = (V, E) with k colours is a mapping c : V-->{1,..., k} such that c(u) ≠ c(v) for every (u, v) ϵ E. Consider the following statements: (i) If every vertex in G has degree at most d, then G admits a vertex colouring using d+1 colours. (ii) Every cycle admits a vertex colouring using 2 colours. (iii) Every tree admits a vertex colouring using 2 colours. Which of the above statements is/are TRUE? Choose from the following options.
A
only (i)
B
only (i) and (ii)
C
only (i) and (iii)
D
only (ii) and (iii)
E
(i), (ii), and (iii)
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2017
Question 197
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on n vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles?
A
n
B
n(n-1)/2
C
n!
D
2n
E
2m ,where m=n(n-1)/2
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2017
Question 198
For an undirected graph G = (V, E), the line graph G∗ = (V ∗, E∗) is obtained by replacing each edge in E by a vertex, and adding an edge between two vertices in V ∗ if the corresponding edges in G are incident on the same vertex. Which of the following is TRUE of line graphs?
A
the line graph for a complete graph is complete
B
the line graph for a connected graph is connected
C
the line graph for a bipartite graph is bipartite
D
the maximum degree of any vertex in the line graph is at most the maximum degree in the original graph
E
each vertex in the line graph has degree one or two
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2017
Question 199
Which of the following graphs DOES NOT have an Eulerian circuit? (Recall that an Eulerian circuit in an undirected graph is a walk in the graph that starts at a vertex and returns to the vertex after travelling on each edge exactly once.)
A
K9,9
B
K8,8
C
K12,12
D
K9
E
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}.
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2016
Question 200
An undirected graph G = (V, E) is said to be k-colourable if there exists a mapping c : V -->{1, 2, . . . , k} such that for every edge {u, v}ϵE we have c(u) ≠ c(v). Which of the following statements is FALSE?
A
G is |V |-colourable
B
G is 2-colourable iff there are no odd cycles in G
C
G is (∆ + 1)-colourable where ∆ is the maximum degree in G
D
There is a polynomial time algorithm to check if G is 2-colourable
E
If G has no triangle then it is 3-colourable
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2016
Question 201
Let G be an undirected graph. For a pair (x, y) of distinct vertices of G, let mincut(x, y) be the least number of edges that should be deleted from G so that the resulting graph has no x-y path. Let a, b, c be three vertices in G such that mincut(a, b) ≤ mincut(b, c) ≤ mincut(c, a). Consider the following possibilities: (i) mincut(a, b) < mincut(b, c) < mincut(c, a) (ii) mincut(a, b) = mincut(b, c) < mincut(c, a) (iii) mincut(a, b) < mincut(b, c) = mincut(c, a) (iv) mincut(a, b) = mincut(b, c) = mincut(c, a) Which of the following is TRUE?
A
All of (i), (ii), (iii), (iv) are possible
B
(i), (ii), (iii) are possible but not (iv)
C
(i) and (iv) are possible but neither (ii) nor (iii)
D
(ii) and (iv) are possible but neither (i) nor (iii)
E
(iii) and (iv) are possible but neither (i) nor (ii)
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2016
Question 202
Let Kn be the complete graph on n vertices labelled {1, 2,. .., n} with m = n(n — 1)/2 edges. What is the number of spanning trees of Kn?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2015
Question 203
In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph G?
A
There are even number of vertices of even degree
B
There are odd number of vertices of even degree
C
There are even number of vertices of odd degree
D
There are odd number of vertices of odd degree
E
All the vertices are of even degree
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2012
Question 204
Which of the following graphs are bipartite?
A
Only (1)
B
Only (2)
C
Only (2) and (3)
D
None of (1),(2), (3)
E
All of (1), (2), (3)
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2020
Question 205
Let G be an undirected graph. An Eulerian cycle of G is a cycle that traverses each edge of G exactly once. A Hamiltonian cycle of G is a cycle that traverses each vertex of G exactly once. Which of the following must be true?
A
Checking if G has an Eulerian cycle can be done in polynomial time
B
Deciding if G has a Hamiltonian cycle is not NP-complete
C
If G has an Eulerian cycle, then it has a Hamiltonian cycle
D
A complete graph always has both an Eulerian cycle and a Hamiltonian cycle
E
All of the other statements are true
       Engineering-Mathematics       Graph-Theory       TIFR PHD CS & SS 2020
Question 206
How many subgraphs with at least one vertex does a labeled complete graph with 3 vertices have?
A
7
B
10
C
12
D
17
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2017
Question 206 Explanation: 
No. of graphs with one verex = 1
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 11-1 = 10
Question 207
Consider that 135 cities in India are to be connected by high-speed fibre optic links. Each link will connect a pair of cities so that the entire. network of 135 cities is connected. The additional requirement is that the network will remain connected if any single link fails. What is the minimum number of links needed to set up the network?
A
268
B
9045
C
270
D
135
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2017
Question 207 Explanation: 
Total no. of minimum links required to make the network of cities connected is 135 in the cycle form.So even if one singe link get fails then also the network will remain connected.
Question 208
Consider a weighted undirected graph G with positive edge weights. Let (u, v) be an edge in the graph. It is known that the shortest path from a vertex s to u has weight 35 and the shortest path from s to v has weight 56. Which of the following is always true?
A
Weight of (u, v) ≤ 21
B
Weight of (u, v) = 21
C
Weight of (u, v) ≥ 21
D
Nothing can be said about the weight of (u,v)
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2017
Question 208 Explanation: 
Question 209
Consider a graph G with six vertices. Which of the following sequences can not represent the degree of its vertices
A
3, 3, 3, 2, 2, 1
B
3, 3, 3, 3, 2, 2
C
3, 3, 3, 2, 2, 2
D
3, 2, 2, 2, 2, 1
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2017
Question 209 Explanation: 
by applying Havel hakimi theorem we could easily find out the incorrect sequence.
Question 210
The number of paths of length 3 between two different vertices in K4 is
A
7
B
6
C
9
D
8
       Engineering-Mathematics       Graph-Theory       HCU PHD CS 2018 June
Question 210 Explanation: 


Question 211

The adjacency matrix of the following graph is:


A
B
C
D
All of the above
       Engineering-Mathematics       Graph-Theory       HCU PHD CS 2018 June
Question 211 Explanation: 
Adjacency matrix for the given graph is
Question 212

What is true for the following graphs




A
(i) is planar but (ii) is not
B
Both are planar
C
(ii) is planar but (i) is not
D
Both are not planar
       Engineering-Mathematics       Graph-Theory       HCU PHD CS 2018 June
Question 212 Explanation: 
Let’s check for graph 1st,

Yes, it is planar. Let's check for graph 2nd,
Yes, it is also planar.
Question 213
It is not possible to construct a graph having
A
Even number of nodes with even degree
B
Even number of nodes with odd degree
C
Odd number of nodes with even degree
D
Odd number of nodes with odd degree
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2015
Question 213 Explanation: 
A graph is possible if sum of degree of vertices is even. But if we add odd number of vertices each with odd degree then sum will be odd,hence for this graph is not possible.
Question 214
Let G be a connected graph with "v" nodes and "e" edges. The number of edges to be dropped to form a tree are
A
e - v + 1 where e < v
B
e - v + 1 where e >= v
C
v - e + 1 where e < v
D
v - e + 1 where e >=v
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2015
Question 214 Explanation: 
For a tree no. of edges should be v-1. So if e is the total no. of edges ,then no. of edes to be removed to make the graph a tree is e-(v-1) = e-v+1.Moreover according to the question the graph is connected and not the tree then definitely e>=v. Hence option B is the answer.
Question 215
Let G be an Eulerian weighted graph with sum of the weights of edges as 1000. What is the weight of Eulerian circuit of G
A
Eulerian circuit need not exist
B
Eulerian circuit exist with weight greater than 1000
C
Eulerian circuit exist with weight less than 1000
D
Eulerian circuit exist with weight equal to 1000
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2015
Question 215 Explanation: 
In eulerian circuit each edge of eulerian graph is used exactly once.So since the given graph is eulerian weighted graph ,so the cost or weight of each edges will be used exactly once,and sum of all edge weigts given as 1000.Hence the weight of eulerian circuit is 1000.
Question 216
A simple graph on 8 vertices is given such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be degree of the last vertex
A
3
B
0
C
5
D
4
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2015
Question 216 Explanation: 
We know that that for a graph to be valid sum of degree of vertices should be even. Now degree of seven vertices are given whose sum is 1+2+3+4+5+6+7 = 28.So the other vertex will be of even degree .Now option A and C are rejected. Now the answer is out of B and D.Now we will use havel hakemi theorem to check that the graph with given sequence including the last vertex is possible or not.
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
A connected planar graph with 15 vertices divides the plane into 12 regions. How many edges does the graph have
A
15
B
24
C
25
D
Insufficient data
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2015
Question 217 Explanation: 
For a planar connected graph the formula is n-e+f = 2,
Where,
n=no. of vertices=15
e=no. of edges
f=no. of regions=12
Hence no. of edges is ,
n-e+f = 2
=>15-e+12=2
=>27-e=2
=>e=25
Question 218
Let Knbe the complete graph on n vertices. Then which of the following is not true ?
A
Kn has n(n-1)/2 edges
B
Kn is Eulerian for all n ≥ 5
C
Kn is Hamiltonian for all n ≥ 5
D
Kn is Non-planar for all n ≥ 5
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2016
Question 218 Explanation: 
Option B is false because the condition for the graph to be eulerian is that the degree of each vertices must be even and the graph must be connected. But the graph K6 will have vertices of odd degree.So option B is false.
Question 219
The number of cut-vertices in a tree with n vertices and m leaves is
A
n+m
B
n
C
m
D
n-m
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2016
Question 219 Explanation: 
The cut vertices is the vertices which disconnects the graph into two or more connected componenets.So leaves can never disconnect tree but internal node can do.So no. of cut vertices in a tree with n vertices and m leaves = n-m.
Question 220
Which of the following can be sequences of degree of vertices in a simple connected graph with 6 vertices.
A
5,4,4,3,2,1
B
5,4,4,3,2,2
C
5,4,4,3,2,0
D
7,5,1,4,2,2
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2016
Question 220 Explanation: 
Apply havel hakemi theorem and you will get option B as the answer.
Question 221
What is True for a complete bipartite graph K(3,3)?
A
it is a planar graph
B
it requires three colours to be minimally coloured
C
it is non-planar
D
it is isomorphic to K(2,4)
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2014
Question 221 Explanation: 
The graph K(5) and K(3,3) are two of the most important graphs within the subject of planarity in graph theory.Kuratowski’s theorem tells us that if we can find the subgraph in any graph that is homeomorphic to K(5) or K(3,3) then the graph is not planar,meaning its not possible for the edges to be redrawn such that they are none overlapping. Of course this theorem relies on the fact that K(5) and K(3,3) are themselves are not planar.
Question 222
Which of the following is NOT TRUE with respect to a simple graph?
A
Every fully connected graph is a tree
B
Every minimally connected graph is a tree
C
Every graph with n nodes and n-1 edges is a tree
D
Every connected graph with no cycles is a tree
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2014
Question 222 Explanation: 
A is false because fully connected graph or complete graph with more than 2 vertices is having cycles,But tree do not have cycles.
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 n-1 edges can have cycles if the graph is disconnected.
D is true.
Question 223
A tree has x vertices of degree 1,2 vertices of degree 2,4 vertices of degree 3 and 3 vertices of degree 4. What is the value of x?
A
12
B
10
C
8
D
Cannot be computed
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2013
Question 223 Explanation: 
Total no. of vertices = x + 2 + 4 + 3 = 9 + x
In a tree of n vertices no. of edges is n-1.
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
A sequence d=(d1,d2,...,dn) is called graphic if there is a simple undirected graph with degree sequence d. Which of the following are not valid graphic sequences?
A
(2, 3, 3, 4, 4, 5)
B
(2, 3, 4, 4, 5)
C
(1, 3, 3, 3)
D
(1, 2, 2, 2,3)
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2013
Question 224 Explanation: 
By using the havel hakimi theorem we can show that only the sequence given in option D is valid and rest are invalid.
Question 225
What is the maximum number of edges in a simple undirected bipartite graph of n nodes?
A
nC2
B
⌊n^2/4 ⌋
C
⌊n^2/2⌋
D
⌊n/2⌋
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2013
Question 225 Explanation: 
Maximum no. of edges in a simple undirected bipartite graph of n nodes is (n/2) * (n/2) = n^2 /4,which is closest to the option B.
Question 226
The length of a Hamiltonian path (if exists) in a simple connected graph of n vertices is
A
n+1
B
n-1
C
n
D
None of the above
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2012
Question 226 Explanation: 
Hamiltonian path is a path in a graph that visits each vertex exactly once.
So if each vertex is visited exactly once then to cover those vertices exactly n-1 edges are required,because if vertices are not repeated then edge will also be not repeated.
Question 227
what is the maximum possible number of directed edges in an n-node, simple, acyclic, directed graph?
A
n-1
B
3n
C
nC2
D
n(n - 1)
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2012
Question 227 Explanation: 
The maximum possible number of directed edges in an n-node, simple, acyclic, directed graph is n(n-1)/2 which is also can be written as nC2.
Question 228
What is the maximum possible number of edges in an n-node, simple, acyclic, undirected graph?
A
n-1
B
⌊n/2⌋ * ⌈n/2⌉
C
nC2
D
n(n - 1)
       Engineering-Mathematics       Graph-Theory       HCU PHD CS MAY 2012
Question 228 Explanation: 
The maximum possible number of edges that can be possible in an n-node, simple ,acyclic ,undirected graph is n-1.If we try to any more edges in it then it will form a cycle.
Question 229
A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Assume we are dealing with finite, undirected, simple graphs with at least two vertices. A graph is connected if there is a path between any two vertices in the graph, and is disconnected otherwise. The complement G' of a graph G has the same vertex set as G, and contains an edge {u, v} if and only if G does not contain the edge {u, v}. For the first and third questions below, you will get the credit only if you also provide the justification. If your answer is yes, drawing an example of such a graph G and its complement G' suffices as the justification. If your answer is no, then you should argue why this is the case.
(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.
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CMI 2020
Question 229 Explanation: 
(a) No, there are no such graphs. Let G be a disconnected graph, and let u, v be two vertices in G such that there is no path in G from u to v. Let Cu be the set of vertices of the connected component of G to which u belongs, and let R = V (G) \ Cu be the rest of the vertices. Then v ∈ R and no vertex in Cu has a neighbour in R. So in G every vertex in Cu is a neighbour of every vertex in R. If |Cu| = 1 then this means that G is connected. So let |Cu| ≥ 2.
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
A graph is finite if it has a finite number of vertices, and simple if it has no self-loops or multiple edges. Prove or disprove: There exists a finite, undirected, simple graph with at least two vertices in which each vertex has a different degree. To give a proof it suffices to draw an example of such a graph. To disprove the result, you should provide an argument as to why such a graph cannot exist.
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CMI 2020
Question 230 Explanation: 
There are no such graphs. If G is such a graph on n vertices then the possible degrees for its vertices are 0, 1, . . . ,(n − 1), and since there are exactly n of these values, all of them must appear as a degree of some vertex exactly once. If a vertex of G has degree (n − 1) then it must be adjacent to every other vertex in G, and in this case no vertex can have the degree 0. So G cannot exist.
Question 231
Consider the following statements about finite simple graphs G:
(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?
A
(i) only
B
(ii) only
C
both (i) and (ii)
D
neither of them
       Engineering-Mathematics       Graph-Theory       CMI 2021
Question 231 Explanation: 
(i) Let P = ⟨v1, v2, . . . , vt⟩ be a maximal path in G. Since vt has degree at least 2 in G, there is an edge {vt, x} in G which is different from the edge incident on vt in the path P. Since P is a maximal path the vertex x must belong to P. So x = vi for some 1 ≤ i < (t − 1). The path ⟨vi, v(i+1), . . . , vt⟩ together with the edge {vt, vi} forms a cycle in G.
(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
One day, Dumbledore assigns Harry Potter the task of obtaining the Philosopher’s Stone that lies in an inner chamber surrounded by many rooms. To guide him along, he is given the Marauder’s Map which contains the following graph.
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?
A
4 colors for walls and 4 colors for the rooms
B
3 colors for walls and 4 colors for the rooms
C
2 colors for walls and 3 colors for the rooms
D
2 colors for walls and 5 colors for the rooms
       Engineering-Mathematics       Graph-Theory       CMI 2021
Question 232 Explanation: 
Consider the undirected graph G where every vertex corresponds to a wall and there is a edge between two vertices whenever two walls are incident on (or adjacent to) each other. Now, coloring for walls is the same as coloring the vertices of G such that no two adjacent vertices get the same color. This can be done with 3 colors and the graph G is often called the line graph (of the image given above).
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 4-Color Theorem.
Question 233
A cut edge of a connected graph G is any edge e = {u, v} of G such that the graph G − e obtained by deleting edge e (and not deleting u or v) is disconnected. In fact, G−e will have exactly two connected components. Let G be an arbitrary finite simple connected graph in which every vertex has an odd degree, and let e be an arbitrary cut edge of G. Let H1, H2 be the two connected components of G − e. Prove or disprove the following statement:
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.
A
Descriptive explanation
       Engineering-Mathematics       Graph-Theory       CMI 2021
Question 234
You are organizing a party involving 2n diplomats. Each pair of diplomats are either friends or enemies. You have managed to invite an excellent set of guests, each of whom has more friends than enemies (among the other guests). Can you now seat them at a round table so that everyone has two friends as their Neighbours. (Hint: Model this situation as an appropriate graph so that the desired seating arrangement is a Hamiltonian path.)
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory       CMI PHD 2022
Question 234 Explanation: 
Let the wizards be numbered 1, . . . , 2n. Form a graph G = (V,E) with V = {1, . . . , 2n} and E = {(i, j) | i and j are friends}. Treat the edges to be undirected. Since each wizard has more friends than enemies, it means that the degree of each vertex in G is at least n. If we find a Hamiltonian cycle in this graph, we can seat wizards around the table so that each wizard has friends on both sides. By Dirac’s Theorem, We know that a Hamiltonian cycle always exists for such graphs. A proof of this fact can be found here.
Question 235
Let G = (V,E) be an undirected simple graph. A subset M ⊆ E is a matching in G if distinct edges in M do not share a vertex. A matching is maximal if no strict superset of M is a matching. How many maximal matchings does the following graph have?
A
1
B
2
C
3
D
4
E
5
       Engineering-Mathematics       Graph-Theory       TIFR PHD 2022
Question 236
We are given a graph G along with a matching M and a vertex cover C in it such that |M| = |C|. Consider the following statements:
(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?
A
Only statement (1) is correct
B
Only statement (2) is correct
C
Only statement (3) is correct
D
Only statements (1) and (2) are correct
E
All the three statements (1), (2), and (3) are correct
       Engineering-Mathematics       Graph-Theory       TIFR PHD 2022
There are 236 questions to complete.