Electrical Engineering (EE) Exam  >  Electrical Engineering (EE) Tests  >  GATE Electrical Engineering (EE) Mock Test Series 2025  >  Test: Graph Theory- 2 - Electrical Engineering (EE) MCQ

Test: Graph Theory- 2 - Electrical Engineering (EE) MCQ


Test Description

12 Questions MCQ Test GATE Electrical Engineering (EE) Mock Test Series 2025 - Test: Graph Theory- 2

Test: Graph Theory- 2 for Electrical Engineering (EE) 2024 is part of GATE Electrical Engineering (EE) Mock Test Series 2025 preparation. The Test: Graph Theory- 2 questions and answers have been prepared according to the Electrical Engineering (EE) exam syllabus.The Test: Graph Theory- 2 MCQs are made for Electrical Engineering (EE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Graph Theory- 2 below.
Solutions of Test: Graph Theory- 2 questions in English are available as part of our GATE Electrical Engineering (EE) Mock Test Series 2025 for Electrical Engineering (EE) & Test: Graph Theory- 2 solutions in Hindi for GATE Electrical Engineering (EE) Mock Test Series 2025 course. Download more important topics, notes, lectures and mock test series for Electrical Engineering (EE) Exam by signing up for free. Attempt Test: Graph Theory- 2 | 12 questions in 30 minutes | Mock test for Electrical Engineering (EE) preparation | Free important questions MCQ to study GATE Electrical Engineering (EE) Mock Test Series 2025 for Electrical Engineering (EE) Exam | Download free PDF with solutions
Test: Graph Theory- 2 - Question 1

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.

Detailed Solution for Test: Graph Theory- 2 - Question 1

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.

Test: Graph Theory- 2 - Question 2

How many perfect matchings are there in a complete graph of 6 vertices?

Detailed Solution for Test: Graph Theory- 2 - Question 2

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 K6, we have
Number of perfect matchings = 

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Graph Theory- 2 - Question 3

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

Detailed Solution for Test: Graph Theory- 2 - Question 3


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

Test: Graph Theory- 2 - Question 4

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?

Detailed Solution for Test: Graph Theory- 2 - Question 4

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

Test: Graph Theory- 2 - Question 5

Detailed Solution for Test: Graph Theory- 2 - Question 5

Test: Graph Theory- 2 - Question 6

Which of the following graphs has an Eulerian circuit?

Detailed Solution for Test: Graph Theory- 2 - Question 6

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) C25 has 24 edges and each vertex has exactly 2 degrees. So every vertex in the complement of C25 will have 24 - 2 = 22 degrees which is an even number.
Since every vertex in the complement of C25 has even degrees. Also, the complements of all Cn with n ≥ 5 is connected. So, it is an Euler graph.

Test: Graph Theory- 2 - Question 7

G is a simple, connected, 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

Detailed Solution for Test: Graph Theory- 2 - Question 7

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.

Test: Graph Theory- 2 - Question 8

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?

Detailed Solution for Test: Graph Theory- 2 - Question 8

Havel Hakimi theorem:
Arrange the degree of vertices in descending order
eg. d1, d2, d3... dn
Discard dand subtract '1' from the next 'di' 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.

Test: Graph Theory- 2 - Question 9

Which of the following graphs is isomorphic to

Detailed Solution for Test: Graph Theory- 2 - Question 9

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.

Test: Graph Theory- 2 - Question 10

Which of the following statements is/are TRUE for undirected graph?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

Detailed Solution for Test: Graph Theory- 2 - Question 10

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

Test: Graph Theory- 2 - Question 11

An ordered n-tuple (d1, d2, .... dn) with d1 ≥ d≥ ... ≥ 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?

Detailed Solution for Test: Graph Theory- 2 - Question 11

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

Test: Graph Theory- 2 - Question 12

If G is a forest with n-vertices and k connected components, how many edges does G have?

Detailed Solution for Test: Graph Theory- 2 - Question 12

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

25 docs|247 tests
Information about Test: Graph Theory- 2 Page
In this test you can find the Exam questions for Test: Graph Theory- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Graph Theory- 2, EduRev gives you an ample number of Online tests for practice

Top Courses for Electrical Engineering (EE)

Download as PDF

Top Courses for Electrical Engineering (EE)