GATE CSE 2021 Set 1 | Graph Theory Question 15 | Discrete Mathematics

GATE CSE 2021 Set 1

MCQ (More than One Correct Answer)

-0

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Root of T is an articulation point in G if and only if it has 2 or more children.

Root of T can never be an articulation point in G.

A leaf of T can be an articulation point in G.

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.67

Let G be a group order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?

G is always cyclic, but H may not be cyclic.

G may not be cyclic, but H is always cyclic.

Both G and H are always cyclic.

Both G and H may not be cyclic.

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.67

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:

diam(G) = $$\displaystyle\max_{u, x\in V}$$ {the length of shortest path between u and v}

Let M be the adjacency matrix of G.

Define graph G₂ on the same set of vertices with adjacency matrix N, where

$$N_{ij} =\left\{ {\begin{array}{*{20}{c}} {1 \ \ \text{if} \ \ {M_{ij}} > 0 \ \ \text{or} \ \ P_{ij} > 0, \ \text{where} \ \ P = {M^2}}\\ {0, \ \ \ \ \ \text{otherwise}} \end{array}} \right.$$

Which one of the following statements is true?

diam(G) < diam(G₂) ≤ diam(G)

$$\left\lceil {diam(G)/2} \right\rceil $$ < diam(G₂) < diam(G)

diam(G₂) ≤ $$\left\lceil {diam(G)/2} \right\rceil $$

diam(G₂) = diam(G)

GATE CSE 2020

Numerical

-0

Graph G is obtained by adding vertex s to K_3,4 and making s adjacent to every vertex of K_3,4. The minimum number of colours required to edge-colour G is _____.

Your input ____