## Graph-Theory

 Question 1
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
Question 1 Explanation:
 Question 2
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______
 A 11
Question 2 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 3

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

 A d*n/2
Question 3 Explanation:
Sum of degree of vertices = 2 × no. of edges
d * n = 2 * |E|
∴ |E| = d*n/2
 Question 4

The number of distinct simple graphs with upto three nodes is

 A 15 B 10 C 7 D 9
Question 4 Explanation:
 Question 5

Prove that in finite graph, the number of vertices of odd degree is always even.

 A Theory Explanation.
 Question 6

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
Question 6 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 7

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
Question 7 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 8

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
Question 8 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 9

Which of the following graphs is isomorphic to

 A B C D
Question 9 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 10

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
Question 10 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 11

Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i - j| = 8 or |i - j| = 12. The number of connected components in G is

 A 8 B 4 C 12 D 25
Question 11 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 12

(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.
 Question 13

Let (A, *) be a semi group. Furthermore, for every a and b in A, if a ≠ b, then a*b ≠ b*a.

(a) Show that for every a in A

` a*a = a `

(b) Show that for every a, b in A

` a*b*a = a  `

(c) Show that for every a, b, c in A

` a*b*c = a*c `
 A Theory Explanation.
 Question 14

Let G be a connected, undirected graph. A cut in G is a set of edges whose removal results in 0 being broken into two or more components which are not connected with each other. The size of a cut is called its cardinality. A 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.
 Question 15

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.
 Question 16

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
Question 16 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 17

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
Question 17 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 18

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
Question 18 Explanation:
We need 2 colours to colour even cycle and 3 colours to colour odd cycle.
 Question 19

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
Question 19 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 20

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

 A 15 B 24 C 30 D 60
Question 20 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 21

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
Question 21 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 22

(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.
 Question 23

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.
 Question 24

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
Question 24 Explanation:

The above graph with 5 vertices and 10 edges is non-planar.
 Question 25

Maximum number of edges in a planar graph with n vertices is ________

 A 3n - 6
Question 25 Explanation:
The maximum is 3(n - 8) for every n>2.
⇒ (3n - 2) = 3n - 6
 Question 26

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

 A (n-k)(n-k+1)/2
Question 26 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 27

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
Question 27 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 28

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
Question 28 Explanation:
Maximum number of edges in an acyclic undirected graph = No. of vertices - 1
= n - 1
 Question 29

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
Question 29 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 30

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
Question 30 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 31

Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is

 A 1/(2n-1) B 1/n C 2/n D 3/n
Question 31 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 32

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
Question 32 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 33

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
Question 33 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 34

What is the chromatic number of the following graph?

 A 2 B 3 C 4 D 5
Question 34 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 35
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.
Question 35 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 36
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.)
Question 36 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 37
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
 Question 38
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
Question 38 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 39

Which of the following graphs is/are planner?

 A Theory Explanation is given below.
Question 39 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 40

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.
Question 40 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 41

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
Question 41 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 42

How many graphs on n labeled vertices exist which have at least (n2 - 3n)/2 edges?

 A B C D
Question 42 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 43

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
Question 43 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 44

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
Question 44 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 45

Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?

 A In any planar embedding, the number of faces is at least n/2 + 2 B In any planar embedding, the number of faces is less than n/2 + 2 C There is a planar embedding in which the number of faces is less than n/2 + 2 D There is a planar embedding in which the number of faces is at most n/(δ+1)
Question 45 Explanation:
Euler’s formula:
v – e + f = 2 →①
Point ① degree of each vertex is minimum ‘3’.

3×n ≥ 2e
e ≤ 3n/2
From ① :
n-3n/2+f = 2 ⇒
 Question 46

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
Question 46 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 47

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
Question 47 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 48

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
Question 48 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 49

Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is _______________.

 A 24 B 25 C 26 D 27
Question 49 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 50

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

 A 4 B 5 C 6 D 7
Question 50 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 51
Let G be a simple, finite, undirected graph with vertex set {v1,...,vn}. Let Δ(G) denote the maximum degree of G and let N = {1, 2,...} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1,...,n
color(vi) ← min{j ε N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE?
 A This procedure results in a proper vertex coloring of G. B The number of colors used is at most Δ(G) + 1. C The number of colors used is at most Δ(G). D The number of colors used is equal to the chromatic number of G.
 Question 52

G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.

 A 16 B 17 C 18 D 19
Question 52 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 53

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
Question 53 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 54

The chromatic number of the following graph is _______.

 A 1 B 2 C 3 D 4
Question 54 Explanation:
Chromatic number of the following graph is “3”
 Question 55

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

 A n! B 1 C (n-1)! D
Question 55 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 56

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
Question 56 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 57

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)
Question 57 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 58

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
Question 58 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 59

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
Question 59 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 60

Which one of the following graphs is NOT planar?

 A G1 B G2 C G3 D G4
Question 60 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 61

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
Question 61 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
There are 61 questions to complete.

Register Now