Graph Theory MCQ Quiz - Objective Question with Answer for Graph Theory - Download Free PDF

Data:

sum of degree in a graph = dsum

number of edges in a graph  = e

Formula:

By handshaking lemma:

dsum = 2 × e

Calculation

sum of odd degree + sum of even degree = 2× e 

sum of odd degree = 2× e - sum of even degree 

2 × e → is even

sum of even degree  → even

even - even = even

Therefore the sum of odd degrees is even and hence the number of odd degree vertices is even too.

Therefore option 1 is false

The correct answer is option 3: 196

Key Points

• A maximal planar graph is a planar graph in which no more edges can be added without violating planarity.
• In a maximal planar graph with \( n \) vertices:
  • Number of edges = \( 3n - 6 \)
  • From Euler’s formula: \( V - E + F = 2 \)
• Given \( V = 100 \)
• So, edges \( E = 3 \cdot 100 - 6 = 294 \)
• Apply Euler's formula: \( 100 - 294 + F = 2 \Rightarrow F = 196 \)

Additional Information

• This maximum occurs because all faces in a maximal planar graph are triangles.
• Each triangle shares edges with others, making the total number of faces dependent on total edges and vertices.

Hence, the correct answer is: option 3: 196

Concept:

For a simple connected maximal planar graph with \( n \) vertices:

The graph is a triangulation, meaning every face (except possibly the outer one) is a triangle.

In such graphs, the number of edges \( e \) is given by:

\( e = 3n - 6 \)

Using Euler's formula:

\( n - e + f = 2 \)

Given:

\( n = 100 \)

So, number of edges:

\( e = 3(100) - 6 = 294 \)

Now, apply Euler's formula to find faces:

\( f = 2 - n + e = 2 - 100 + 294 = 196 \)

Final Answer: ✅ 196

The correct answer is A and B only.

Key Points

• A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
• Planar graphs follow Kuratowski's theorem, which states that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K₅ (complete graph on five vertices) or K_3,3 (complete bipartite graph on six vertices).
• To determine if a graph is planar, one can try to draw it in such a way that no edges cross each other, except at the vertices.

Additional Information

• Graphs A and B are determined to be planar by verifying that they can be drawn without any edge crossings.
• Graph C is not planar because it contains a subgraph that is homeomorphic to K₅ or K_3,3, which means it cannot be drawn without edge crossings.
• Planar graphs are useful in various fields such as computer networking, geography, and circuit design, where planar embeddings help to minimize complexity and avoid intersections.
• Graph theory provides various algorithms to check for planarity, such as the Hopcroft and Tarjan planarity testing algorithm.

The correct answer is Option 1.

Key Points

• Complete Graph (K_n): Has n(n−1)/2 edges.
• Cycle Graph (C_n): Has n edges.
• Wheel Graph (W_n): Has 2(n−1) edges.
• Complete Bipartite Graph (K_n,n): Has n² edges.
• n-Cube Graph (Q_n): Has n × 2ⁿ⁻¹ edges.

Additional Information

• Let us verify using n = 5:

• Now arranging based on increasing number of edges:
• → Cycle (5) < Wheel (8) < Complete (10) < Complete Bipartite (25) < n-Cube (80)
• So, the correct answer is: B,C,A,D,E.

Given:

The edges of the polyhedron = 30

The faces of the polyhedron = 12

Formula used:

Euler's formula for the polyhedron

F + V = E + 2      (Where F = The face of the polyhedron, V = The vertices of the polyhedron, and E = The edge of the polyhedron)

Calculation:

Let be assume the vertices of the polyhedron is V

⇒ 12 + V = 30 + 2

⇒ V = 32 - 12 = 20

∴ The required result will be 20.

Data:

number of faces = |F|

number of vertices  = |V| = 10

edges covering each face = 3

Formula:

According to Euler’s formula : 

|V| - |E|  + |F| = 2

Calculation

edges on each face is three

∴ 2 |E| = 3 |F|       (every edge is shared by 2 faces)

\(|F| = \frac{2}{3} |E|\)

\(10 - E + \frac{2}{3}|E|=2\)

|E| = 24

the number of edges in G is 24

Given:

Population in states in 2010 depicted in a pie- chart.

Total population = 16200000

Calculation:

Rajasthan has 180° of population.

So, 16200000 × ( 180 / 360 ) 

= 8100000

∴ Rajasthan's population in year 2010 is 8100000

In a directed graph G Strongly connected will have a path from each vertex to every other vertex.

If the direction of the edges is reverse, then also graph is strongly connected components as G

Option 2: G₂ = (V, E₂) where E₂ = {(u, v)|(v, u) ∈ E}

In this option G₂, edges are reversed and hence it is a strongly connected components as similar to G

So, changing the direction of all the edges, won't change the SCC.

Edge coloring for a graph refers to assigning colors to the graph edges in a way that no two incident edges have same color.

A K_3,4 graph looks like

To edge color this graph properly, we will consider every edge from vertex set of max(u, v). In our case, max(3, 4) will be 4.

Hence from u1, 4 edges of different colors (Red, Black, blue, Green) are incident on v1, v2, v3, v4.

Similarly, 4 edges of different colors (Red, Green, Black, Blue) are incident on v1, v2, v3, v4.

Now adding a new vertex s which is adjacent to all the vertices will require 7 different colors of edges. But we can still use Red, Green, Brown, Blue and 3 other colors.

Hence, maximum colors required for edge-coloring in a planar graph is directly related to the maximum degree of the graph, therefore, MAX (3, 4, 7) = 7

Important Point:

The question is asking about edge coloring and not about vertex coloring.

A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit.

In Hamiltonian cycle is a Hamiltonian circuit in which initial and final vertex are same.

In an undirected complete graph on n vertices, there are n permutations are possible to visit every node. But from these permutations, there are: n different places (i.e., nodes) you can start; two (clockwise or anticlockwise) different directions you can travel. So, any one of these n! cycles is in a set of 2n cycles which all contain the same set of edges.

(A) FALSE:

e.g.

The only edge in the above tree is bridge.

(B) TRUE:

If an edge is the part of the cycle than its removal will not disconnect the graph.

(C) FALSE:

e.g. 

Here no edge of the clique is a bridge

(D) FALSE:

e.g. 

Concept:-

Isomorphic graphs:-

If two graphs have some numbers of nodes and the some numbers of branches and they look different but have some incidence matrix called isomorphic graphs

This is the same incidence matrix for both the graphs

Additional Information

Tree:- Tree is a connected subgraph of a given graph, which contains all the nodes of a graph, but then should in no any loop in the subgraph called a tree.

Data

Number of vertices = V = 8

Number of faces = 5

Number of edges = E

Euler's formula:

V + F = E + 2

Calculation

⇒ E = V + F - 2

⇒ E = 8 + 5 - 2

⇒ E = 11 

∴ Number of edges is 11