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

Maximum components will result after 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 vis 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 a lone 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.

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)

For n = 3, 2n = 6, i.e. complete graph K₆, we have
Number of perfect matchings = 

Clearly the minimum degree has to be less than 6 always and hence cannot be equal to 6.

Sum of degree of all vertices = 2e (using Handshaking lemma)
So, 6 x 2 + 3 x 4 + x x 3 = 2 x 27
12 + 12 + 3x = 54
3x = 54 - 24
x = 30/3
x = 10
So, total number of vertices
⇒ x + 6 + 3 = 10 + 6 + 3 = 19

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, kregular graph need not be connected, hence k-regular may not contain Euler circuit.
(b) Complete graph on 90 vertices not contains 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 is connected. So, it is an Euler graph.

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 graph, so degree of all odd degree vertices now become even and degree of vertex v is also even (since number of odd degree vertex are even).
Now all vertices in the graph are of even degree and graph is connected, so it must be Eular graph.

Havel Hakimi theorem:
Arrange the degree of vertices in descending order
eg. d₁, d₂, d₃... d_n
Discard d₁ and subtract '1' from the next 'd_i' degrees
Ex:3,2,2,1,1

discard degree 3 and subtract one from the next highest 3 degrees. It means removing a vertex of degree 3 that refers to removing 3 edges in the graphs.
So, 1,1,0,1

0,0,1,0  We should not get any negative value if it's negative, this is not a valid sequence, and Repeat it till we get the '0' sequence.

Option 1: 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,0

Hence true.
Option 2:  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
3, 0, 0, 0, 1 (descending order)
3,1,0,0,0
0,-1,-1,0

Hence False.
Option 3: 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
Hence True.
Option 4: 8, 7, 7, 6, 4, 2, 1, 1
There is a degree 8 but there are only '8' vertices. A vertex cannot have an edge to itself in a simple graph. This is not a valid sequence.

Hence False.

The correct answer is II and IV.

Check invariants are one by one.
Step 1: All 4 choice have same number of vertices and edges as given graph.
Step 2: So we find degree sequence of 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 given graph, since degree sequence of these graphs is not same as given graph.
Step 3: Now to decide between options (b) and (d), which one is isomorphic to 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 given Graph.

Q is Hand-shaking theorem and hence true.
P is a corollory to the Hand-shaking theorem and hence also true.

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

The number of edges in spanning forest of a graph G with n vertices and k components = Rank (G) = n - k .