From the Graph of G State at Which Points the Graph is Not Continues and Why Quiz

Computer Science Graph Theory MCQ Quiz Questions and Answers PDF Download

Question 1.
Which of the following graphs is/are planar? (see Figure)

(a) G1 only
(b) G1 and G2
(c) G2 only
(d) G2 and G3

Answer/Explanation

Answer: (c) G2 only
Explanation:

G₁ is k_{3, 3} which is a well-known non-planar graph.

Graph G₂ is isomorphic to the following graph:

The above graph is planar. So G₂ is planar.

G₃ is isomorphic to K_{3, 3} which is well known non-planar graph. Therefore, G₃ is a non-planar graph.

---

Question 2.
A graph is planar if and only if,
(a) If does not contain subgraphs homeomorphic to K₅ and K_{3, 3}.
(b) It does not contain subgraphs isomorphic to K₅ or K_{3, 3}.
(c) It does not contain subgraphs isomorphic to K₅ and K_{3, 3}.
(d) It does not contain subgraph homeomorphic to K₅ or K_{3, 3}.

Answer/Explanation

Answer:(d) It does not contain subgraph homeomorphic to K₅ or K_{3, 3}.
Explanation:
Kuratowski's theorem: A graph is planar if and only if, it does not contain a subgraph homeomorphic to K₅ or K_{3, 3}.

---

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

Answer/Explanation

Explanation:
The maximum number of possible edges in an undirected graph with "a" vertices and "k" components is \(\frac{(a-k+1)(a-k)}{2}\)

---

Question 4.
A non-planar graph with a 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

Answer/Explanation

Answer:(c) 10 edges, 5 vertices
Explanation:
K₅ is the smallest non-planar graph in terms of the number of vertices. The number of vertices in K₅ is 5 and number of edges in K₅ is \(\frac{5 \times 4}{2}\) = 10

---

Question 5.
The maximum number of edges in a planar graph with n vertices is ________.

Answer/Explanation

Explanation:
The maximum number of edges in a connected, planar, simple graph with n vertices is 3n – 6.

---

Question 6.
The number of distinct simple graphs with up to three nodes is
(a) 15
(b) 10
(c) 7
(d) 9

Answer/Explanation

Answer:(c) 7
Explanation:
Assume that the vertices are unlabelled. Number of distinct simple graphs with 1 node = 1

Therefore, total number of distinct simple graphs up to three nodes = 1 + 2 + 4 = 7.

---

Question 7.
Prove that in a finite graph, the number of vertices of odd degrees is always even.

Answer/Explanation

Explanation:
According to the Handshaking theorem, for a graph G = (V, E) with n vertices and e edges then

Let Ve and V0 respectively the set of vertices of even degree and the set of vertices of odd degree in an undirected graph G = (V, E) then

Since deg(v) is even for v∈V_e, the first sum on the right-hand side of the equality is even. The total sum must be 2e, which is even, so the second sum must be even too. But all of its terms are odd so there must be an even number of them.

---

Question 8.
Let G be an undirected connected graph with distinct edge weights. Let e_max be the edge with maximum weight and e_min be the edge with minimum weight. Which of the following statements is false?
(a) Every minimum spanning tree of G must contain e_min
(b) If e_max is in a minimum spanning tree, then its removal must disconnect G
(c) No minimum spanning tree contains e_max
(d) G has a unique minimum spanning tree

Answer/Explanation

Answer:(c) No minimum spanning tree contains e_max
Explanation:
(a) All the edge weights are distinct, so every minimum spanning tree of G must contain e_min (Kruskal's algorithm will pick e_min first)
(b) If e_max is in a minimum spanning tree, then surely its removal must disconnect G (i.e. e_max must be a cut edge).
(c) A minimum spanning tree can contain e_max if its removal disconnects G (i.e. it is a cut edge). So this option is false.
For example, in the graph given below, the edge cd is a maximum weight edge but still is present in the minimum spanning tree.

(d) Since all edge weights are distinct G has a unique minimum spanning tree.

---

Question 9.
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v₁, v₂, ……. v_n} of n vertices?
(a) \(\frac{\mathrm{n}(\mathrm{n}-1)}{2}\)
(b) 2ⁿ
(c) n!
(d) 2 \(\frac{\mathrm{n}(\mathrm{n}-1)}{2}\)

Answer/Explanation

Answer:(d) 2 \(\frac{\mathrm{n}(\mathrm{n}-1)}{2}\)
Explanation:
In a graph G with n vertices, maximum number of edges possible = \(\frac{n(n-1)}{2}\)
There are two ways for a edge, (the edge may appear in graph or may absent in graph). So there are two options for each edge.
Total number of graphs with n vertices = 2\(\frac{n(n-1)}{2}\)

---

Question 10.
Maximum number of edges in a n-node undirected graph without self loops is
(a) n²
(b) n(n – 1)/2
(c) n – 1
(d) (n + 1) (n)/2

Answer/Explanation

Answer:(b) n(n – 1)/2
Explanation:
The graph containing a maximum number of edges in an n-node undirected graph without self-loops is a complete graph. The number of edges incomplete graph with n-node, k_n is \(\frac{n(n-1)}{2}\).

---

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

Answer/Explanation

Answer:(c) k – 1 and n – 1
Explanation:
Maximum components will result after the removal of a node if graph G is a star graph as shown below.

or a null graph of n vertices as shown below:

In either case, if node v is removed, the number of components will be n – 1, where n is the total number of nodes in the star graph.
∴ n – 1 is the maximum number of components possible. Minimum components will result if the node being removed is alone vertex in which case, the number of components will be k – 1.
∴ The number of components must necessarily lie between k – 1 and n – 1.

---

Question 12.
How many perfect matchings are there in a complete graph of 6 vertices?
(a) 15
(b) 24
(c) 30
(d) 60

Answer/Explanation

Answer:(a) 15
Explanation:
The number of perfect matchings in a complete graph of n vertices, where n is even, reduces to the problem of finding unordered partitions of the vertex set of the type p(2n; 2, 2,2,… n times) = \(\frac{(2 n) !}{(2 !)^{n} n !}\)
For n = 3, 2n = 6, i.e. complete graph k6, we have
Number of perfect matchings = \(\frac{6 !}{(2 !)^{3} 3 !}\)
=\(\frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{2 \times 2 \times 2 \times 6}\) = 15

---

Question 13.
A Graph G = (V, E) satisfies | E | ≤ 3 |V| – 6. The min-degree of G is defined as min {degree (v)}. Therefore, min-degree of G cannot be
(a) 3
(b) 4
(c) 5
(d) 6

Answer/Explanation

Answer:
(d) 6
Explanation:
Given |E| < 3 | V| — 6 …(i)
Let δ be the minimum degree of the graph. Now δ cannot exceed the average degree of the graph.
so, \(\delta \leq \frac{2|\mathrm{E}|}{|\mathrm{V}|}\)
Substitute eq. (i) in eq. (ii) and get
\(\delta \leq \frac{2}{|\mathrm{~V}|}\)(3|V|-6)
⇒ δ ≤ 6 – \(\frac{12}{|\mathrm{~V}|}\)
Clearly the minimum degree has to be less than 6 always and hence cannot be equal to 6.

---

Question 14.
The minimum number of colors required to color the following graph, such that no two adjacent vertices are assigned the same color, is

(a) 2
(b) 3
(c) 4
(d) 5

Answer/Explanation

Answer:
(c) 4
Explanation:
An assignment of the colors 1, 2, 3, and 4 to the vertices of the graph is shown below such that the graph is properly colored.

So 4 colors are required.
(Note: The graph is a planar graph. The four-color theorem says that the chromatic number of a planar graph is at most = 4).

---

Question 15.
How many graphs on n labeled vertices exist which have at least (n² – 3n)/2 edges?

Answer/Explanation

Answer:

Explanation:
Take number of edges available in n labelled vertices is
nc2 = \(\frac{n(n-1)}{2}\) = \(\frac{\mathrm{n}^{2}-\mathrm{n}}{2}\) edges
Now from this we need to choose \(\frac{\mathrm{n}^{2}-\mathrm{3n}}{2}\) edges
or more upto a maximum of \(\frac{\mathrm{n}^{2}-\mathrm{n}}{2}\) edges. Each such choice of edges represents a distinct graph on n labelled vertices.
Total number of such graphs

---

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

Answer/Explanation

Answer:
(a) n – 1
Explanation:
Acyclic graphs are graphs that do not contain cycles. For a maximum number of edges, each vertex connects to another vertex only if it does not form a cycle i.e. from a tree with n vertices, which has maximum n – 1 edge. Ex. with 4 vertices, 3 edges maximum.

---

Question 17.
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 the remaining of degree 3?
(a) 10
(b) 11
(c) 18
(d) 19

Answer/Explanation

Answer:
(d) 19
Explanation:
Sum of degree of all vertices = 2e (using Handshaking lemma)
So, 6 × 2 + 3 × 4 + x × 3 = 2 × 27
12 + 12 +3x = 54
3x = 54 – 24
x = \(\frac { 30 }{ 3 }\)
x = 10
So, total number of vertices
⇒ x + 6 + 3 = 10 + 6 + 3 = 19

---

Question 18.
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) 0
(b) 8
(c) 9
(d) 13

Answer/Explanation

Answer:
(b) 8
Explanation:
Given V = 13, E = 19
Let R be the number of regions.
R =E – V + 2
⇒ R = 19 -13 +2
= 8

---

Question 19.
Which one of the following graphs is NOT planner?

Answer/Explanation

Explanation:
G₁ is the same as K_{3, 3} which is known to be non-planar. G₂, G_3, and G₄ can be redrawn as follows so that they are planar.

---

Question 20.
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a
(a) Hamiltonian cycle
(b) Grid
(c) Hypercube
(d) Tree

Answer/Explanation

Answer:
(d) Tree
Explanation:
If the subset of edges connects all the vertices and it has minimum total weight then it never forms a cycle. So it is called a tree.

---

Question 21.
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/(2^{n – 1})
(b) 1/n
(c) 2/n
(d) 3/n

Common Data for Q.4.22 & Q.4.24
The 2n vertices of graph G correspond 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.

Answer/Explanation

Answer:
(c) 2/n
Explanation:
The hamming distance relation on bit strings has a digraph which will be always an n-cube where n is the number of bits.
An achromatic number of n-cube = 2 (since n-cube is always bipartite). Also the diameter of n- cube = n. So the ratio of a chromatic number to the diameter of the n-cube = 2/n.

---

Question 22.
The number of vertices of degree zero in G is
(a) 1
(b) n
(c) n + 1
(d) 2ⁿ

Answer/Explanation

Answer:
(c) n + 1
Explanation:
Let S contains n elements then S have 2ⁿ subsets. Graph G contains 2ⁿ vertices.
Let S = {v₁; v₂,…, v_n}. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
So |{V_i} ∩ {V_j}| =2
For this to happen, the subset must have at least 2 elements. There are n sets that contain a single element for V₁ to V_n who doesn't intersect another set such that it contains two elements. Therefore the degree of all these n vertices is zero. G also contains a vertex Φ whose degree is zero. So the number of vertices whose degree is zero is n + 1.

---

Question 23.
The maximum degree of a vertex in G is
(a) \(\left(\begin{array}{c}
\mathrm{n} / 2 \\
2
\end{array}\right)\) 2n/2
(b) 2^{n – 2}
(c) 2^{n – 3} × 3
(d) 2^{n – 1}

Answer/Explanation

Answer:
(c) 2^{n – 3} × 3
Explanation:
Let the set be S = {1, 2, 3, 4, …, n}
Consider a subset containing 2 elements of the form {1, 2}. Now {1, 2} will be adjacent to any subset with which it has exactly 2 elements in common. These sets can be formed by adding zero or more elements from the remaining n – 2 elements, to the set {1, 2}. Since each of these elements may be either added or not added, the number of ways of making such sets containing 1 and 2 is 2n – 2.

∴ Vertices with 2 elements will have 2n – 2 degrees.

Now consider subsets of 3 elements say {1, 2, 3}. Since we want exactly 2 elements in common, we choose these in ³C₂ ways, and then we can add or not add the remaining n-3 elements. This can be done in 2n – 3 ways.

∴ A total number of subsets with at least 2 elements common with {1, 2, 3} is given by ³C₂ × 2n – 3.

Similarly, we can argue that the number of degrees of 4 element subsets is ⁴C₂ × 2n – 4 and for 5 element subsets is ⁵C₂ × 2n – 5, and so on.

Out of these 2n – 2 = 2 . 2n – 3 is less than ³C₂ × 2n – 3 = 3 × 2n – 3.

Then ³C₂ × 2n – 3 = 3 × 2n – 3 is same as ⁴C₂ × 2n – 4 = 6 × 2n – 4 = 3 × 2n – 3 and ⁴C₂ × 2n – 4 = 3 × 2n – 3 is greater than ⁵C₂ × 2n – 5 = 10 × 2n – 5 = 2.5 × 2n – 3 maximum degree in this graph is occurring for 3 element and 4 element subsets both of which have 3 × 2n – 3 degree.

---

Question 24.
The number of connected components in G is
(a) n
(b) n + 2
(c) 2^n/2
(d) 2ⁿ/n

Answer/Explanation

Answer:
(b) n + 2
Explanation:
The number of the connected components of G is determined by the degree and edges of vertices there are n + 1 vertices whose degree is zero, so they can form n + 1 connected component. The remaining vertices of graph G are all connected as a single component. So the total number of the connected components is n + 2.

---

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

Answer/Explanation

Answer:
(b) 9 edges and 6 vertices
Explanation:
K₅ and K_3,3 are the smallest nonplanar graphs. K₅ has 5 vertices and ⁵C₂ = 10 edges and K_3,3 has 6 vertices and 3 × 3 = 9 edges. So, the non-planar graph with the minimum number of edges is K_3,3 with 9 edges and 6 vertices.
Note: K₅ is the non-planar graph with a minimum number of vertices.

---

Question 26.
Consider the DAG with V = {1, 2, 3, 4, 5, 6}, shown below:

Which of the following is NOT a topological ordering?
(a) 123456
(b) 132465
(c) 1 3 2 4 5 6
(d) 3 2 4 1 6 5

Answer/Explanation

Answer:
(d) 3 2 4 1 6 5
Explanation:
In topological sorting the partial ordering of the DAG must be preserved i.e. if a ≤ b is in the DAG, then in the topological order, b must come after a, not before. Consider the ordering 3 2 4 16 5. 1 ≤ 4 in the given DAG but 4 is coming before 1 in 3 2 4 1 6 5 order which means that 3 2 416 5 is not a topological order of the given DAG.

---

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

Answer/Explanation

Answer:
(c) The complement of a cycle on 25 vertices
Explanation:
Whenever in a graph all vertices have even degrees, it will surely have an Euler circuit.
(a) Since in a k-regular graph, every vertex has exactly k degrees and if k is even, every vertex in the graph has even degrees, k- regular graph need not be connected, hence k-regular may not contain Euler circuit.
(b) Complete graph on 90 vertices does not contain an Euler circuit, because every vertex degree is odd (89)
(c) C₂₅ has 24 edges and each vertex has exactly 2 degrees. So every vertex in the complement of C₂₅ will have 24 – 2 = 22 degrees which is an even number.
Since every vertex in the complement of C₂₅ has even degrees. Also, the complements of all C_n with n ≥ 5 are connected. So, it is an Euler graph.

---

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

Answer/Explanation

Answer:
(b) 4
Explanation:

Maximum independent sets:
{a, c, e, g, i} and {b, d, f, h}.
Smallest maximum independent set {b, d, f, h}. Size = 4

---

Question 29.
What is the chromatic number of the following graph?

(a) 2
(b) 3
(c) 4
(d) 5

Answer/Explanation

Answer:
(b) 3
Explanation:
Since there is a 5-cycle (odd cycle) in this graph, this graph is not bipartite and hence its chromatic number is at least 3. A proper coloring with 3 colors, is shown below:

Hence a minimum number of colors needed to color the given graph is equal to 3.

---

Question 30.
G is a simple, connected, undirected graph. Some vertices of G are of odd degrees. 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

Answer/Explanation

Answer:
(d) Euler
Explanation:
In an undirected simple, connected graph number of vertices must be even of odd degree (using Handshaking lemma). Adding a vertex v, adjacent to all odd degree vertices in the graph, so the degree of all odd degree vertices now become even and the degree of vertex v is also even (since the number of odd degrees vertex are even). Now all vertices in the graph are of even degree and the graph is connected, so it must be a Eular graph.

---

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

Answer/Explanation

Answer:
(a) 2
Explanation:
If an n-vertex simple connected graph contains no cycles of odd length, then its chromatic number is two since the vertices can be alternately colored with the first color, then the second color, then the first color, and then the second color, and so on.
Alternatively, since a simple connected graph with no cycles of odd length must be bipartite, and since the chromatic number of a non-null bipartite graph is always 2 (in a bipartite graph each partition requires one color (there are no edges within a partition of a bipartite graph) and there are only two partitions).
Note: Since it is given that the graph is connected, it cannot be a null graph (Φ_n)

---

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

Answer/Explanation

Answer:
(b) At least two vertices have the same degree
Explanation:
In a simple connected undirected graph (with more than two vertices), at least 2 vertices must have the same degree, since if this is not true, then all vertices would have different degrees. A graph with all vertices having different degrees is not possible to construct (can be proved as a corollary to the Havell-Hakimi theorem). Notice that it is possible to construct graphs satisfying choices a, c and d.

---

Question 33.
Let, G = (V, E) be a graph. Define ε(G) = \(\sum_{d} i_{d}\) × 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

Answer/Explanation

Answer:
(c) |S| = |T|
Explanation:
Given, IMG = Sum of degrees By handshaking theorem, ξ(G) = 2 |E_G| where, | E_G| is the number of edges in G. If S and T are two trees with ξ(S) = ξ(T).
⇒ 2 |E_s| = 2|E_T|
⇒ |E_s| = |E_T|
In a tree, | E_s| = |S| – 1 and | E_T| = | T | – 1 Where | S | is number of vertices of tree S and |T| is number of vertices of tree T.
∴ |S| – 1 = |T| – 1
⇒ |S| = |T|

---

Question 34.
In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
(a) 0
(b) 1
(c) (n – 1)/2
(d) n – 1

Answer/Explanation

Answer:
(a) 0

Explanation:
A tree with 1 node is not possible, since it is given that every node has exactly 1 child. Now consider a tree with 2 nodes (a is the root)

Now a has exactly one child. A number of descendants of a = 2. But this contradicts the given fact that every node has an odd number of Descendents. Now consider a tree with 3 nodes. Since every – node has exactly one child, it must be of the form,

Here a has 3 descendants, b has 2 descendants and c has one. Again we have a contradiction in that b does not have an odd number of descendants. Similarly can show that for trees with 4, 5, 6 … nodes, it is not possible to have all nodes with an odd number of descendants. So the correct answer is the tree has 0 nodes, i.e., choice (a).

---

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

Answer/Explanation

Answer:
(d) II and IV
Explanation:
Havell-Hakimi algorithm can be used to check whether a given degree sequence is a graph or not.
The algorithm is
1. remove the top node of the sequence.
2. subtract "1" from as many nodes in the remaining sequence as the degree of the top node that was removed.
3. rearrange this sequence in nonincreasing order.
4. check if the resulting sequence is a graph.
5. proceed again to step 1.

If the given sequence is not a graph we will see a violation in step 4, such as the presence of negative degrees in the sequence. Otherwise, the algorithm will bottom out with a degree sequence consisting of only an even number of l's and any number of 0's. Now applying the algorithm to the degree sequences I, II, III, and IV, one by one:
I. 7, 6, 5, 4, 4, 3, 2, 1
6, 5, 4, 4, 3, 2, 1                (Step 1)
5, 4, 3, 3, 2, 1, 0                (Step 2)
5, 4, 3, 3, 2, 1, 0                (Step 3)
The sequence is a graph  (Step 4)
4, 3, 3, 2, 1, 0                    (Step 1)
3, 2, 2, 1, 0, 0                    (Step 2)
3, 2, 2, 1, 0, 0                    (Step 3)
The sequence is a graph (Step 4)
2, 2, 1, 0, 0                       (Step 1)
1, 1, 0, 0, 0                       (Step 2)
1, 1, 0, 0, 0                       (Step 3)
A sequence is a graph     (Step 4)

Now, the algorithm ends, since the sequence has only 0's and an even a number of l's. The final sequence corresponds to the following valid graph

Similarly for sequence II.
II. 6, 6, 6, 6, 3, 3, 2, 2
6, 6, 6, 3, 3, 2, 2             (Step 1)
5, 5, 5, 2, 2, 1, 2             (Step 2)
5, 5, 5, 2, 2, 2, 1             (Step 3)
Sequence is a graph     (Step 4)
5, 5, 2, 2, 2, 1                 (Step 1)
4, 4, 1, 1, 1, 1                 (Step 2)
4, 4, 1, 1, 1, 1                 (Step 3)
Sequence is a graph     (Step 4)
4, 1, 1, 1, 1                    (Step 1)
3, 0, 0, 0, 1                    (Step 2)
3, 1, 0, 0, 0                    (Step 3)
Sequence is a graph    (Step 4)
1, 0, 0, 0                       (Step 1)
0,-1,-1,0                       (Step 2)
0, 0, -1, -1                    (Step 3)

The sequence is not a graph (Step 4), since negative degrees are not possible in a valid graph. So, the algorithm ends.
II is cannot be the degree sequence of any graph. Similarly, we can show that III is the degree sequence of some graphs and IV is not the degree sequence of any graph.
So, option (d) is correct.

---

Question 36.
K₄ and Q₃ are graphs with the following structures:

Which one of the following statements is TRUE in relation to these graphs?
(a) K₄ is planar while Q₃ is not
(b) Both K₄ and Q₃ are planar
(c) Q₃ is planar while K₃ is not
(d) Neither K₄ nor Q₃ is planar

Answer/Explanation

Answer:
(b) Both K₄ and Q₃ are planar

Explanation:
The planar embedding of K₄ and Q₃ is shown below:

So both graphs are planar.

---

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

Answer/Explanation

Answer:
(d) 6
Explanation:
n = 10
e = 15
In a simple connected planar graph, Euler's formula gives the total number of regions as e – n + 2 = 15 – 10 + 2 = 7 Out of this, one region is unbounded and the other 6 are bounded. So the correct answer is 6, which is an option (d).

---

Question 38.
Which of the following graphs is isomorphic to

Answer/Explanation

Explanation:
Check invariants are one by one.
Step 1: All 4 choices have the same number of vertices and edges as the given graph.
Step 2: So we find the degree sequence of the given graph which is (1, 1, 2, 2, 2, 2, 2, 4).
Degree sequence of graph in option (a) is (1, 1, 1, 2, 2, 2, 3, 4).
Degree sequence of graph in option (b) is (1, 1, 2, 2, 2, 2, 2, 4)
Degree sequence of graph in option (c) is (1, 1, 2, 2, 2, 2, 3, 3)
Degree sequence of graph in option (d) is (1, 1, 2, 2, 2, 2, 2, 4).
So only options (a) and (c) are not isomorphic to the given graph. since the degree sequence of these graphs is not the same as the given graph.
Step 3: Now to decide between options (b) and (d), which one is isomorphic to the given graph, we check the number of cycles. In given Graph, there is one cycle of length 5 but in Graph (d), there is no cycle of length 5. Graph (b) has one cycle of length 5. So only Graph (b) can be isomorphic to the given Graph.

---

Question 39.
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) 90
(d) 360

Answer/Explanation

Answer:
(d) 360
Explanation:
The graph given is K₆.
In K₆, every cycle of length 4 corresponds to selecting 4 vertices out of 6 vertices, which can be done in ⁶C₄ ways, and then ordering the 4 vertices in circular permutation in 3! ways (since vertices are labeled). So the final answer is ⁶C₄ × 3! = 90.

---

Question 40.
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is \(\frac { 1 }{ 2 }\). What is the
expected numbers of unordered cycles of length three?
(a) \(\frac { 1 }{ 8 }\)
(b) 1
(c) 7
(d) 8

Answer/Explanation

Answer:
(c) 7
Explanation:
We need to find the unordered cycle of length 3 so we choose any 3 vertices from 8 vertices. This can be done in ⁸C₃ ways To make a cycle we need to choose the edge between the selected vertices probability of choosing any edge is \(\frac { 1 }{ 2 }\).
So for three edges = \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) × \(\frac { 1 }{ 2 }\) = \(\frac { 1 }{ 8 }\)
Expected no of cycle = np
Here, n = ⁸C₃ and p = \(\frac { 1 }{ 8 }\)
Expected no of cycles = ⁸C₃ × \(\frac { 1 }{ 8 }\) = 7.

---

Question 41.
Which of the following statements is/are TRUE for an undirected graph?
P: The number of odd degree vertices is even.
Q: The sum of degrees of all vertices is even.
(a) P only
(b) Q only
(c) Both P and Q
(d) Neither P nor Q

Answer/Explanation

Answer:
(c) Both P and Q
Explanation:
Q is the Handshaking theorem and hence true.
P is a corollary to the Handshaking theorem and hence also true.

---

Question 42.
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) G₁ = (V, E₁) where E₁ = {(u,v) | (u,v) ∉ E}
(b) G₂ = (V, E₂) where E₂ = {(u,v) | (v,u)∈ E}
(c) G₃ = (V, E₃) where E₃ = {(u,v) | there is a path of length ≤ 2 from u to v in E}
(d) G₄ = (V₄, E) where V₄ is the set of vertices in G which are not isolated

Answer/Explanation

Answer:
(b) G₂ = (V, E₂) where E₂ = {(u,v) | (v,u)∈ E}
Explanation:
G = (V, E) is directed graph
G₂ = (V, E₂) where E₂ = {(u, v) | (v,u) ∈ E}
G and G2 have the same strongly connected components only the difference in G₂ is that all edges of G have been reversed the direction.

---

Question 43.
Consider an undirected graph G 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 _____.

Answer/Explanation

Explanation:

Explanation:
The given condition translates into the graph shown below where every vertex is connected only with its neighbors.

From the above diagram:

1. The four corner vertices have every 3 degrees which give 4 × 3 = 12 degrees.
2. The 40 side vertices have 5 degrees each contributing a total of 40 × 5 = 200 degrees.
3. The 100 interior vertices each have 8 degrees contributing a total of 100 × 8 = 800 degrees.

So total degree of the graph
12 + 200 + 800 = 1012 degrees
Now the number of edges in any undirected graph = \(\frac{\text { Total deg rees }}{2}\)
Therefore the number of edges in this graph = \(\frac{\text { 1012 }}{2}\) = 506

---

Question 44.
An ordered n-tuple (d₁, d₂,…, d_n) with d₁ ≥ d₂ ≥ … ≥ d_n is called graphic if there exists a simple undirected graph with n vertices having degrees d₁, d₂,…, d_n 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)

Answer/Explanation

Answer:
(c) (3, 3, 3, 1, 0, 0)

Explanation:
Use the Havell-hakimi algorithm.
The sequence of steps in the algorithm for each graph is shown below:

---

Question 45.
The maximum number of edges in a bipartite graph on 12 vertices is _____.

Answer/Explanation

Explanation:
Bipartite graph {u, u} where u and v are partition on vertices:

• {1, 11} ⇒ 1 × 11 = 11 edges maximum
• {2, 10} ⇒ 2 × 10 = 20 edges maximum
• {3, 9} ⇒ 3 × 9 = 27 edges maximum
• {4, 8} ⇒ 4 × 8 = 32 edges maximum
• {5, 7} ⇒ 5 × 7 = 35 edges maximum
• {6, 6} ⇒ 6 × 6 = 36 edges maximum

∴ The maximum number of edges in a bipartite graph on 12 vertices = 36 edges.

---

Question 46.
A cycle on n vertices is isomorphic to its complement. The value of n is ______.

Answer/Explanation

Explanation:
If a graph is isomorphic to its own complement, then it is a self complementary graph. In a self complementary graph e = \(\frac{\text { n(n – 1) }}{4}\)
but in the cycle C_n, e = n.
Som if a cycle is self complementary, then n = \(\frac{\text { n(n – 1) }}{4}\)

The solution of the above equation is n = 5. So, C₅ is the only cycle graph that is self-complementary.

---

Question 47.
The number of distinct minimum spanning trees for the weighted graph below is ______.

Answer/Explanation

Explanation:
The edges with weight 1, do not form a cycle. Take all of them. The weight 2 edges can be chosen in 3 × 2 = 6 ways, as shown below.

Total there is six possible minimum spanning trees. [3 × 2 = 6]

---

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

Answer/Explanation

Answer:
(c) n – k
Explanation:
The number of edges in the spanning forest of a graph G with n vertices and k components = Rank (G) = n – k.

---

Question 49.
Let 8 denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with 8 ≥ 3 which one of the following is TRUE?
(a) In any planar embedding, the number of faces is at least \(\frac { n }{ 2 }\) + 2
(b) In any planar embedding, the number of faces is less than \(\frac { n }{ 2 }\) + 2
(c) There is a planar embedding in which the number of faces is less than \(\frac { n }{ 2 }\) + 2
(d) There is a planar embedding in which the number of faces is at most \(\frac{\mathrm{n}}{\delta+1}\)

Answer/Explanation

Answer:
(a) In any planar embedding, the number of faces is at least \(\frac { n }{ 2 }\) + 2
Explanation:
Σdeg = 2e
Given δ ≥ 3 also δ ≤ 2e/n
⇒ e ≥ nδ/2
⇒ e ≥ 3n/2
Euler's formula:
r = e – n + 2 ≥ 3n/2 – n + 2 ≥ n/2 + 2 So the number of faces is atleast n/2 + 2

---

Question 50.
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 ______.

Answer/Explanation

Explanation:
Number of vertices (n) = 10
d(ri) = 3
Number of edges (e) = ?
r = e – v + 2
(euler's formula for connected planar graphs) r = e – 10 + 2 = e – 8 …(1)
Since every region is bounded by exactly 3 edges and since every edge is exactly double-counted, we have the equation

e = \(\frac { 3r }{ 2 }\) ⇒ r = \(\frac { 2e }{ 3 }\)

Substituting this in equation (1) we get, \(\frac { 2e }{ 3 }\) = e – 8
2e = 3e – 24 ⇒ e = 24

---

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

Answer/Explanation

Answer:
(d) Congruent to 0 mod 4, or 1 mod 4

Explanation:
An n-vertex self-complementary graph has exactly half number of edges of the complete graph i.e.\(\frac { n(n – 1) }{ 4 }\) edges. Since n(n – 1) must be divisible by 4, n must be congruent to 0 mod 4 or 1 mod 4.

---

Question 52.
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 subgraph of a graph)
(d) A graph with bridges cannot have a cycle

Answer/Explanation

Answer:
(b) A bridge cannot be part of a simple cycle
Explanation:
An edge is called a bridge iff it's removal will disconnect the graph into components. In a cycle, there are two paths between every pair of vertices and so removal of an edge from a cycle does not disconnect the cycle. So a bridge cannot be part of a simple cycle.

---

Question 53.
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ________.

Answer/Explanation

Explanation:
n₀ : Number of leaf nodes 0 children.
n₁ : Number of nodes with 1 child.
n₂ : Number of nodes with 2 children.
We have following two equations for binary tree n = n₀ + n₁ + n₂ (where n is the total number of nodes in the tree) …(1)
Accounting for total nodes as sum of those nodes which are children and the root which is not a child of any node,
we get n = n₁ × 1 + n₂ × 2 + 1 = n₁ + 2n₂ + 1 ….(2)
Combining equations (1) and (2) we get
n₀ + n₁ + n₂ = n₁ + 2n₂ + 1
⇒ n₂ = n₀ – 1

Therefore the number of nodes of degree two in any binary tree = number of leaf nodes -1.
n₂ = 200 – 1 = 199

---

Question 54.
Let G be connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes _______.

Answer/Explanation

Explanation:
G has |V| = 100 vertices and |E| = 300 edges the weight of MST of G = 500 In MST:
Number of vertices = 100
Number of edges = 99
If each edge of G is increased by 5 then MST weight also increased. For each edge of old MST increased by 5.
Total 99 edges.
So 99 × 5 = 445 is increased Total weight of new MST = 500 + 445 = 995

---

Question 55.
The minimum number of colors that is sufficient to vertex-color any planar graph is _________.

Answer/Explanation

Explanation:
The four-color theorem says that every planar graph can color with 4 colors i.e. four colors are sufficient to properly color any planar graph.

---

Question 56.
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ______.

Answer/Explanation

Explanation:
Here in this tree, n = 10
Σdegree = 2 |E|
where |E| represents number of edges. In a tree, |E| = n – 1
= 10 – 1 = 9
So, Σdegree = 2 × 9 = 18

---

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

Answer/Explanation

Explanation:
The number of vertices: n ≤ ?
Number of vertices: |E| = 25
Now since each vertex has at least 3 degree and 2|E| = Σdegree
i.e., 2|E| ≥ 3n
n ≤ 2 |E| / 3
⇒ n ≤ \(\frac { 2 × 25 }{ 3 }\) ≤ 16.66

---

So n is at most 16.

Question 58.
The chromatic number of the following graph is _____.

Answer/Explanation

Explanation:

Since the largest complete subgraph is K₃, the chromatic number is at least 3. We can try for a chromatic number of 3 by using 3 colors, as follows:

Since we have successfully, properly colored all vertices with only 3 colors, the chromatic number of this graph is 3.

---

Question 59.
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 = _______.

Answer/Explanation

Explanation:
The graph has 100! vertices in which each vertex is labeled by one of the 100! permutation. Let us find the degree of each vertex. Let us take a vertex whose labeling is say 1,2,3,4,100. Now it will be connected to all vertices where exactly 2 of the adjacent numbers are all swapped. The two swapped numbers could be (1,2), (2, 3), (3, 4), etc. up to (99, 100) which makes for 99 edges for each such vertex. So the graph is a regular graph with each vertex connected to 99 other vertices. So y=99 The number of connected components = z = 1 since we can go from any vertex to any other vertex by only swapping 2 adjacent numbers at a time, many times i.e. there is a path from any vertex to any other vertex. The graph is connected. So z1 So y + 10z = 99+10 × 1 = 109

---

Question 60.
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) (n – 1)!
(c) 1
(d) \(\frac{(n-1) !}{2}\)

Answer/Explanation

Answer:
(c,d)

Explanation:
• When vertices are labeled.
In a complete graph, we can traverse the n vertices in any order and return to the starting vertex and form a Hamiltonian cycle. The number of such cycles will be n\ However since circular rotations will have to ignore. Since for example K₄ with vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is same as 2-3-4-1 is same as 3-4-1-2 etc. we now get only (n – 1)! distinct Hamiltonian cycles. Further, the cycles 1-2-3-4 and 1-4-3-2 are also the same (clockwise and anticlockwise).
So ignoring this orientation also we finally get \(\frac { (n – 1)! }{ 2 }\) distinct Hamiltonian cycles which is option (d).

• When vertices are unlabelled.
All the Hamiltonian cycles are formed which is isomorphic to each other. So only 1 Hamiltonian cycle will be the answer in this case. So both options (c) and (d) are correct.

---

Question 61.
Graph G is obtained by adding vertex s toK_{3, 4} and making s adjacent to every vertex of K_{3, 4}. The minimum number of colors required to edge- color G is ______.

Answer/Explanation

Explanation:

7 edges are touching at S each of which needs to be colored by a different color. So 7 colors minimum are required. All other vertices have less than 7 edges touching. So 7 colors only are required for edge coloring.

---

Question 62.
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________.

Answer/Explanation

Explanation:
In a connected planar graph
r = e – n + 2
Here, n = 8, r = 5
∴ 5 = e – 8 + 2
e = 11

---

Question 63.
Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as diam(G) = {the length of the shortest path between u and v}
Let M be the adjacency matrix of G. Define graph G₂ on the same set of vertices with adjacency matrix N, where

Which one of the following statements is true?

(a) ["diam(G) / 2] < diam(G₂) < diam(G)
(b) diam(G₂) ≤ [diam(G) / 2]
(c) diam(G) < diam(G₂) ≤ 2 diam(G)
(d) diam(G₂) = diam(G)

Answer/Explanation

Answer:
(b) diam(G₂) ≤ [diam(G) / 2]

Explanation:

Means G₂ will have not only all the edges in G but also will have edges connecting vertices in G which have a path of length 2, since M2 will have all edges between u and v if there is a path of length 2 between shown in G.

option (a) [diam(G)/2] < diam(G₂) < diam(G) Let G be the graph shown below with dia(G) = 2

Since (a,c) has a path of length 2 in G, G₂ will have an edge connecting a and c. Now diameter of G₂ = 1
This violates option (a) condition that dia(G₂)> dia(G)/2 So option (a) false.

option (b) diam(G₂) ≤ [diam (G)/2] consider graph below with dia(G) = 3

Now G₂ will connect all paths of length 2 with edges and will be

Now dia(G₂) = 2
But dia(G) = 3
dia (G₂) = 2 ≤ [dia(G)/2]
2 ≤ [1.5]
2 ≤ 2 satisfied.

option (b) is correct.

Option (c) diam(G) < diam (G₂) ≤ 2 diam (G) Taking previous option example where dia (G) = 3 and dia (G₂) = 2

3 ≤ 2 ≤ 6

Is false.
So option (c) is false.

Option(d) diam (G₂) = diam (G)
Taking previous example where dia(G) = 3 and dia (G₂) = 2
2 = 3 is false.
So option (d) is false.
So correct option is an option (b).

---

deanfenii1989.blogspot.com

Source: https://btechgeeks.com/graph-theory-questions-and-answers/