Test: Graph Theory - Computer Science Engineering (CSE) MCQ

• The number of nodes present in a graph will be equal to the number of principal nodes present in an electric circuit.
• The number of branches present in a graph will be less than or equal to the number of branches present in an electric circuit.
• In a graph there is one and only one path between every pair of vertices.
• Branches are the connections between nodes. A branch is an element(resistor, capacitor, source).
• The number of branches in a circuit is equal to the number of elements.

Option 1: The diagonal entries of A² are the degrees of the vertices of the graph.
True, Assume the adjacency matrix representation of the undirected graph is "A". A²= A x A
Diagonal elements of A² are the degree of vertices or (A_ij²) represents the degree of node i.

K is adjacency matrix is,

Degree sequence of (p,q,r)= (1,2,1)
Diagonal elements= (1,2,1)

Option 2: If the graph is connected, then none of the entries of An-1 + In can be zero.
False, 
Take the following connected graph with n=3,

K is adjacency matrix is, 

We can see that K^n-1+I_n have some entries as zero.
Option 3: If the sum of all the elements of A is at most 2(n - 1), then the graph must be acyclic.
False, Consider following acyclic graph with n=5

A is  adjacency matrix is,

So sum of all elements in A=8
here n=5, So 2(n-1)=2(5-1)=8
Here above graph satisfies the condition of the graph but the above graph is not acyclic.
Option 4: If there is at least a 1 in each of A’s rows and columns, then the graph must be connected.
False, Consider following acyclic graph with n=5

Consider the above graph in A all rows and columns have at least A 1 but it disconnected the graph. Hence the given option is false.
Hence the correct answer is the diagonal entries of A² are the degrees of the vertices of the graph.

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)

the number of edges in G is 24

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 G2, 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.

According to the property of planar graph and four colour theorems. Maximum number of colours that are needed to vertex-colour any planar graph is 4.

Example:
In this graph, only 3 colours are enough to colour this planar graph.

But if in this graph, there is an edge from a to d also, then three colours are not enough to vertex-colour this graph.

In this graph, 4 colours are needed to vertex- colour this graph.

(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:
eg. 

Maximum number of edges in a bipartite graph of n vertices

Example:
n = 6

Number of edges = 6²/4 = 9 

active power (P) = 20 kW
V_ph = 230 V
V_L = 230√3 V
power factor (cosϕ ) =  0.8.
cosϕ = P/S
S = P\cosϕ = 20/0.8 = 25 KVA
Then;

Also

Path is defined as a subgraph consisting of an ordered sequence of branches with the feature that all internal nodes (or vertex) have exactly two subgraph branches.
Only one branch is incident at each of the two terminal nodes (or vertex).

Option 1:The chromatic number of the graph is 3.
True, the Chromatic number of the Peterson graph is 3. We colour the graph with three colours (B, G, R).

Option 2: The graph has a Hamiltonian path.
True, A Hamilton Path is a path that goes through every vertex of a graph exactly once. A Hamilton Circuit is a Hamilton path that begins and ends at the same vertex. 
The Peterson graph has a Hamiltonian path but not a Hamiltonian cycle.
From above graph,
Hamiltonian path= F-B-A-I-E-D-H-G-J

Option 3:The following graph is isomorphic to the Peterson graph.
True, If the adjacency matrices of two graphs are identical, they are said to be isomorphic or If the respective sub-graphs created by removing certain vertices of one graph and their corresponding images in the other graph are isomorphic, then the two graphs are isomorphic.
The given graph is isomorphic to Peterson's graph.

Option 4: The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)
False, A vertex independent set is a set of vertices that are not adjacent. Maximal vertex independent set is a set in which we cannot add one more vertex to it. So, the largest independent set of the Peterson graph is 4.
Hence the correct answer is options 1,2 and 3.