Graph-Theory
Question 1 |
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 _____.
7 |
Question 1 Explanation:
In k3x4 there are two sets with sizes 3,4. (its 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 ( K 3x4 has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
The vertex in the set of size 3 has 4 edges connected to 4 vertices on other set. So, edge color of G is max(3,4) i.e. 4.
When a vertex is added to the graph with 7 vertices ( K 3x4 has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
Question 2 |
The chromatic number of the following graph is _______.
1 | |
2 | |
3 | |
4 |
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 = ___________.
109 | |
110 | |
111 | |
112 |
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
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it.
So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
Question 4 |
G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.
16 | |
17 | |
18 | |
19 |
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)
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 ________.
4 | |
5 | |
6 | |
7 |
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.
Here it is asked about the sufficient number of colors, so with the worst case of 4 colors we can color any planar graph.
Question 6 |
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is _______________.
24 | |
25 | |
26 | |
27 |
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
|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 tree has no bridges | |
A bridge cannot be part of a simple cycle | |
Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph) | |
A graph with bridges cannot have a cycle
|
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
∴ (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 multiple of 4 | |
Even | |
Odd | |
Congruent to 0 mod 4, or, 1 mod 4
|
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?
G1=(V,E1) where E1={(u,v)|(u,v)∉E} | |
G2=(V,E2 )where E2={(u,v)│(u,v)∈E} | |
G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E} | |
G4=(V4,E) where V4 is the set of vertices in G which are not isolated |
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.
→ 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 __________.
506 | |
507 | |
508 | |
509 |
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
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?
(1, 1, 1, 1, 1, 1) | |
(2, 2, 2, 2, 2, 2) | |
(3, 3, 3, 1, 0, 0) | |
(3, 2, 1, 1, 1, 0) |
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.
A) (1, 1, 1, 1, 1, 1)
Yes, it is a graph.
We will see that option (C) is not graphic.
Question 12 |
The maximum number of edges in a bipartite graph on 12 vertices is ______.
36 | |
37 | |
38 | |
39 |
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
Total no. of edges = 6×6 = 36
Question 13 |
A cycle on n vertices is isomorphic to its complement. The value of n is _____.
5 | |
6 | |
7 | |
8 |
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.
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 , in a group ( ,∗) such that every element in the group can be written as a product of some number of x's and 's in some order. It is known that
x*x=y*y=x*y*x=y*x*y*x=e
where is the identity element. The maximum number of elements in such a group is
4 | |
5 | |
6 | |
7 |
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.
a*a-1 = e
1. x*x=e So x-1 is x ⇒ x is element of Group
2. y*y=e So y-1 = y ⇒ y is element of Group
4. (y*x)*(y*x)=x*y*y*x=x*x*e=e So (y*x)-1=(y*x)
In ③, ④
x*y,y*x has same inverse, there should be unique inverse for each element.
x*y=y*x (even with cumulative law, we can conclude)
So {x, y, e, x*y} are element of Group.
Question 15 |
If G is a forest with n vertices and k connected components, how many edges does G have?
⌊n/k⌋ | |
⌈n/k⌉ | |
n–k | |
n-k+1 |
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 : 1edge, which is false.
Option 1, 2 will give answer 1. (i.e. one edge among them),
Option 3: n-k = 0 edges.
Option 4: n-k+1 : 1edge, which is false.
Question 16 |
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
1/8 | |
1 | |
7 | |
8 |
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
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.
P only | |
Q only | |
Both P and Q | |
Neither P nor Q |
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.
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.
Question 18 |
The line graph L(G) of a simple graph G is defined as follows: · There is exactly one vertex v(e) in L(G) for each edge e in G. · For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e'are incident with the same vertex in G. Which of the following statements is/are TRUE?
(P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
P only | |
P and R only | |
R only | |
P, Q and S only |
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.
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
3 | |
4 | |
5 | |
6 |
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.
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
 | |
 | |
 | |
 |
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.
(A) 3 cycle graph not in original one.
(B) Correct 5 cycles & max degree is 4.
(C) Original graph doesn’t have a degree of 3.
(D) 4 cycles not in original one.
Question 21 |
Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to
15 | |
30 | |
45 | |
360 |
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
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?
which one of the following statement is TRUE in relation to these graphs?
K4 is planar while Q3 is not | |
Both K4 and Q3 are planar | |
Q3 is planar while K4 is not | |
Neither K4 not Q3 is planar |
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
|S| = 2|T| | |
|S| = |T| - 1 | |
|S| = |T| | |
|S| = |T| + 1 |
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
I and II
| |
III and IV | |
IV only | |
II and IV |
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.
⇾ 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 |
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
No two vertices have the same degree.
| |
At least two vertices have the same degree. | |
At least three vertices have the same degree. | |
All vertices have the same degree.
|
Question 25 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.
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 26 |
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
2 | |
3 | |
n-1 | |
n |
Question 26 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.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 27 |
Which of the following statements is true for every planar graph on n vertices?
The graph is connected | |
The graph is Eulerian
| |
The graph has a vertex-cover of size at most 3n/4
| |
The graph has an independent set of size at least n/3
|
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.
(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 |
What is the chromatic number of the following graph?
2 | |
3 | |
4 | |
5 |
Question 28 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.
→ 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 29 |
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
5 | |
4 | |
3 | |
2 |
Question 29 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.
(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 30 |
G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be
Regular | |
Complete | |
Hamiltonian | |
Euler |
Question 30 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.
→ 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 31 |
Let G be the non-planar graph with the minimum possible number of edges. Then G has
9 edges and 5 vertices | |
9 edges and 6 vertices | |
10 edges and 5 vertices
| |
10 edges and 6 vertices
|
Question 31 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.
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 32 |
Which of the following graphs has an Eulerian circuit?
Any k-regular graph where k is an even number.
| |
A complete graph on 90 vertices.
| |
The complement of a cycle on 25 vertices.
| |
None of the above.
|
Question 32 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.
→ 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 33 |
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:
 | |
2n-2 | |
2n-3 × 3 | |
2n-1 |
Question 33 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.
(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 34 |
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:
n | |
n+2 | |
2n/2 | |
2n / n |
Question 34 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
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 35 |
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:
1 | |
n | |
n+1 | |
2n |
Question 35 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.
= 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 36 |
Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
1/(2n-1) | |
1/n | |
2/n | |
3/n |
Question 36 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 arbitary points. So the ratio is (2/n).
That will give us a bipartite graph, with chromatic number = 2
Also from the same we can conclude that we need for a 'n' bit string, to traverse no more than (n-1) edges or 'n' vertices to get a path between two arbitary points. So the ratio is (2/n).
Question 37 |
Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
6 | |
8 | |
9 | |
13 |
Question 37 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
F = E - V + 2 [From Euler's formula i.e., F + V - E = 2]
F = 19 - 13 +2
F = 8
Question 38 |
Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
12 | |
8 | |
Less than 8
| |
More than 12
|
Question 38 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
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 39 |
Which one of the following graphs is NOT planar?
G1 | |
G2 | |
G3 | |
G4 |
Question 39 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.
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 40 |
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
There exists a cutset in G having all edges of maximum weight | |
There exists a cycle in G having all edges of maximum weight | |
Edge e cannot be contained in a cycle | |
All edges in G have the same weight
|
Question 40 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.
(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 41 |
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is
4 | |
7 | |
23 | |
99 |
Question 41 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.
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 42 |
2 | |
3 | |
4 | |
5 |
Question 42 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 43 |
 | |
 | |
 | |
 |
Question 43 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)
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 44 |
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 ∪ G2 = (V, E1 ∪ E2)
cannot have a cut vertex
| |
must have a cycle
| |
must have a cut-edge (bridge)
| |
has chromatic number strictly greater than those of G1 and G2
|
Question 44 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.
(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 45 |
What is the maximum number of edges in an acyclic undirected graph with n vertices?
n - 1 | |
n | |
n + 1 | |
2n - 1 |
Question 45 Explanation:
Maximum number of edges in an acyclic undirected graph = No. of vertices - 1
= n - 1
= n - 1
Question 46 |
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?
10 | |
11 | |
18 | |
19 |
Question 46 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
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x - 9) * 3 = 27 * 2
24 + (x - 9) * 3 = 54
x = 19
Question 47 |
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
k and n | |
k – 1 and k + 1 | |
k – 1 and n – 1
| |
k + 1 and n – k
|
Question 47 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.
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n-1) components.
Question 48 |
How many perfect matching are there in a complete graph of 6 vertices?
15 | |
24 | |
30 | |
60 |
Question 48 Explanation:
We have formula to find no. of perfect matchings in complete graphs of 2n vertices,
(2n)!/n!×2n
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×23 = 15
(2n)!/n!×2n
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×23 = 15
Question 49 |
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
Therefore, min-degree of G cannot be3 | |
4 | |
5 | |
6 |
Question 49 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.
|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 50 |
The 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
2 | |
3 | |
4 | |
n - 2[n/2] + 2 |
Question 50 Explanation:
We need 2 colours to colour even cycle and 3 colours to colour odd cycle.
Question 51 |
Maximum number of edges in a n-node undirected graph without self loops is
 | |
 | |
 | |
 |
Question 51 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 53 |
Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are
adjacent if |i - j| = 8 or |i - j| = 12. The number of connected components in G is
8 | |
4 | |
12 | |
25 |
Question 53 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.
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 54 |
The minimum number of edges in a connected cyclic graph on n vertices is:
n - 1 | |
n | |
n + 1 | |
None of the above |
Question 54 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
In cyclic graph:
No. of edges = No. of vertices
⇒ n = n
Question 55 |
The number of distinct simple graphs with upto three nodes is
15 | |
10 | |
7 | |
9 |
Question 55 Explanation:
Question 56 |
The number of edges in a regular graph of degree d and n vertices is _________
d*n/2 |
Question 56 Explanation:
Sum of degree of vertices = 2 × no. of edges
d * n = 2 * |E|
∴ |E| = d*n/2
d * n = 2 * |E|
∴ |E| = d*n/2
Question 57 |
Maximum number of edges in a planar graph with n vertices is ________
3n - 6 |
Question 57 Explanation:
The maximum is 3(n - 8) for every n>2.
⇒ (3n - 2) = 3n - 6
⇒ (3n - 2) = 3n - 6
Question 58 |
A non-planar graph with minimum number of vertices has
9 edges, 6 vertices | |
6 edges, 4 vertices | |
10 edges, 5 vertices | |
9 edges, 5 vertices |
Question 58 Explanation:
The above graph with 5 vertices and 10 edges is non-planar.
Question 59 |
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ...,vn} of n vertices?
 | |
2n | |
n! | |
 |
Question 59 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)
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 60 |
The maximum number of possible edges in an undirected graph with a vertices and k components is ________.
(n-k)(n-k+1)/2 |
Question 60 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
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 61 |
It does not contain subgraphs homeomorphic to k5 and k3,3. | |
It does not contain subgraphs isomorphic to k5 or k3,3. | |
It does not contain a subgraph isomorphic to k5 or k3,3. | |
It does not contain a subgraph homeomorphic to k5 or k3,3. |
Question 61 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 62 |
Theory Explanation is given below. |
Question 62 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.
→ 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.
There are 62 questions to complete.