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

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

Test Description

## 20 Questions MCQ Test GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Test: Graphs Theory- 2

Test: Graphs Theory- 2 for Computer Science Engineering (CSE) 2024 is part of GATE Computer Science Engineering(CSE) 2025 Mock Test Series preparation. The Test: Graphs Theory- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Graphs Theory- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Graphs Theory- 2 below.
Solutions of Test: Graphs Theory- 2 questions in English are available as part of our GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) & Test: Graphs Theory- 2 solutions in Hindi for GATE Computer Science Engineering(CSE) 2025 Mock Test Series course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Graphs Theory- 2 | 20 questions in 60 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Graphs Theory- 2 - Question 1

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

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

Each component will have n/k vertices (pigeonhole principle). Hence, for each component there will be (n/k)-1 edges. Since there are k components, total number of edges= k*((n/k)-1) = n-k.

Test: Graphs Theory- 2 - Question 2

### Let d denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with d ≥ 3, which one of the following is TRUE?

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

Euler's formula for planar graphs:

v − e + f = 2.

v => Number of vertices
e => Number of edges
f => Number of faces

Since degree of every vertex is at least 3, below is true from handshaking lemma (Sum of degrees is twice the number of edges)

3v >= 2e
3v/2 >= e

Putting these values in Euler's formula.
v - 3v/2 + f >= 2

f >= v/2 + 2

Test: Graphs Theory- 2 - Question 3

### The 2n vertices of a graph G corresponds 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. The number of vertices of degree zero in G is:

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

There are n nodes which are single and 1 node which belong to empty set. And since they are not having 2 or more elements so they won’t be connected to anyone hence total number of nodes with degree 0 are n+1 hence answer should be none. Thanks to roger for the explanation.

Test: Graphs Theory- 2 - Question 4

The 2n vertices of a graph G corresponds 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. The number of connected components in G is:

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

n+1 nodes of the graph not connected to anyone as explained in question 70 while others are connected so total number of connected components are n+2 (n+1 connected components by each of the n+1 vertices plus 1 connected component by remaining vertices)

Test: Graphs Theory- 2 - Question 5

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

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

An undirected graph is called a planar graph if it can be drawn on a paper without having two edges cross and such a drawing is called Planar Embedding. We say that a graph can be embedded in the plane, if it planar. A planar graph divides the plane into regions (bounded by the edges), called faces. Graph K4 is palanar graph, because it has a planar embedding as shown in figure below.

Euler's Formula : For any polyhedron that doesn't intersect itself (Connected Planar Graph),the • Number of Faces(F) • plus the Number of Vertices (corner points) (V) • minus the Number of Edges(E) , always equals 2. This can be written: F + V − E = 2. Solution : Here as given, F=?,V=13 and E=19 -> F+13-19=2 -> F=8 So Answer is (B).

Test: Graphs Theory- 2 - Question 6

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum indepen­dent set of G is

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

Background Explanation: Vertex cover is a set S of vertices of a graph such that each edge of the graph is incident to at least one vertex of S. Independent set of a graph is a set of vertices such that none of the vertices in this set have an edge connecting them i.e. no two are adjacent. A single vertex is an independent set, but we are interested in maximum independent set, that is largest set which is independent set. Relation between Independent Set and Vertex Cover : An interesting fact is, the number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set. How? removing all vertices of minimum vertex cover leads to maximum independent set. So if S is the size of minimum vertex cover of G(V,E) then the size of maximum independent set of G is |V| - S. Solution: size of minimum vertex cover = 8 size of maximum independent set = 20 - 8 =12 Therefore, correct answer is (A). References : vertex cover maximum independent set.

Test: Graphs Theory- 2 - Question 7

Which one of the following graphs is NOT planar?

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

A graph is planar if it can be redrawn in a plane without any crossing edges. G1 is a typical example of nonplanar graphs.

Test: Graphs Theory- 2 - Question 8

Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?

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

Suppose shortest path from A->B is 6, but in MST, we have A->C->B (A->C = 4, C->B = 3), then along the path in MST, we have minimum congestion, i.e 4

Test: Graphs Theory- 2 - Question 9

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is

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

Two vertices are said to be adjacent if they are directly connected, i.e., there is a direct edge between them. So, here, we can assign same color to 1 & 2 (red), 3 & 4 (grey), 5 & 7 (blue) and 6 & 8 (brown). Therefore, we need a total of 4 distinct colors. Thus, C is the correct choice.

Please comment below if you find anything wrong in the above post.

Test: Graphs Theory- 2 - Question 10

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: Graphs Theory- 2 - Question 10

Minimum: The removed vertex itself is a separate connected component. So removal of a vertex creates k-1 components. Maximum: It may be possible that the removed vertex disconnects all components. For example the removed vertex is center of a star. So removal creates n-1 components.

Test: Graphs Theory- 2 - Question 11

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

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

A perfect matching, every vertex of the graph is incident to exactly one edge of the matching. A perfect matching is therefore a matching of a graph containing n/2 edges, the largest possible, meaning perfect matchings are only possible on graphs with an even number of vertices.

Test: Graphs Theory- 2 - Question 12

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: Graphs Theory- 2 - Question 12

Let the min-degree of G be x, then G has at least |v| *x/2 edges. |v|*x/2 <= 3* |v| -6 for x=6, we get 0 <= -6, Therefore, min degree of G cannot be 6. Hence answer is (D).

Test: Graphs Theory- 2 - Question 13

The minimum number of colours required to colour the vertices of a cycle with η nodes in such a way that no two adjacent nodes have the same colour is

Detailed Solution for Test: Graphs Theory- 2 - Question 13

We need 3 colors to color a odd cycle and 2 colors to color an even cycle.

Test: Graphs Theory- 2 - Question 14

Maximum number of edges in a n - node undirected graph without self loops is

Detailed Solution for Test: Graphs Theory- 2 - Question 14

Background required - Basic Combinatorics Since the given graph is undirected, that means the order of edges doesn't matter. Since we have to insert an edge between all possible pair of vertices, therefore problem reduces to finding the count of the number of subsets of size 2 chosen from the set of vertices. Since the set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n,2) (also known as "n choose 2"). Using the formula for binomial coefficients, C(n,2) = n(n-1)/2.

Test: Graphs Theory- 2 - Question 15

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 _______________.

Detailed Solution for Test: Graphs Theory- 2 - Question 15

Euler's formula states that if a finite, connected, planar graph is drawn in the plane without any edge intersections, then

v − e + f = 2.
v -> Number of vertices
e -> Number of edges
f -> Number of faces

As per the question v = 10 And number of edges on each face is three Therefore, 2e = 3f [Note that every edge is shared by 2 faces]

Putting above values in v − e + f = 2
10 - e + 2e/3 = 2
e = 3*10 - 6 = 24

Test: Graphs Theory- 2 - Question 16

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is

Detailed Solution for Test: Graphs Theory- 2 - Question 16

An n-vertex self-complementary graph has exactly half number of edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3. Since n(n −1) must be divisible by 4, n must be congruent to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary.

Test: Graphs Theory- 2 - Question 17

In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is True?

Detailed Solution for Test: Graphs Theory- 2 - Question 17

A bridge in a graph cannot be a part of cycle as removing it will not create a disconnected graph if there is a cycle.

Test: Graphs Theory- 2 - Question 18

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: Graphs Theory- 2 - Question 18

The idea is to use Handshaking Lemma :- In any graph, the sum of all the vertex-degree is equal to twice the number of edges.

Let x = Number of vertices of degree 3.
By Handshaking Lemma
6*2 + 3*4 + (x-9)*3 = 27*2
24 + (x-9)*3 = 54
x-9 = 10
x = 19

Test: Graphs Theory- 2 - Question 19

The minimum number of colours that is sufficient to vertex-colour any planar graph is _______________
[This Question was originally a Fill-in-the-blanks Question]

Detailed Solution for Test: Graphs Theory- 2 - Question 19

A planar graph is a graph on a plane where no two edges are crossing each other. The set of regions of a map can be represented more abstractly as an undirected graph that has a vertex for each region and an edge for every pair of regions that share a boundary segment. Hence the four color theorem is applied here. Here is a property of a planar graph that a planar graph does not require more than 4 colors to color its vertices such that no two vertices have same color. This is known four color theorem.

Test: Graphs Theory- 2 - 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

Detailed Solution for Test: Graphs Theory- 2 - Question 20

As here we want subset of edges that connects all the vertices and has minimum total weight i.e. Minimum Spanning Tree Option A - includes cycle, so may or may not connect all edges. Option B - has no relevance to this question. Option C - includes cycle, so may or may not connect all edges. Related:

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

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

### Up next

 Test | 20 ques
 Test | 25 ques
 Test | 15 ques
 Test | 20 ques
 Test | 30 ques

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

152 docs|216 tests

### Up next

 Test | 20 ques
 Test | 25 ques
 Test | 15 ques
 Test | 20 ques
 Test | 30 ques