GATE CS Graphs: Connectivity, Matching, Colouring questions

Practise Graphs: Connectivity, Matching, Colouring questions for GATE CS. Explore official PYQs and original topic-wise quizzes, check answers and view available solutions. Free, no sign-in.

20 on this page

SubjectTopicYearType

G

n

2n-2

edges. The edges of

G

can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for

G

Which of the following statements is true for every planar graph on

n

Which of the following graphs has an Eulerian circuit?

G

be the non-planar graph with the minimum possible number of edges. Then

G

2^n

vertices of a graph

G

corresponds to all subsets of a set of size

n

n \geq 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

2^n

vertices of a graph

G

corresponds to all subsets of a set of size

n

n \geq 6

. Two vertices of

G

are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in

G

2^n

vertices of a graph

G

corresponds to all subsets of a set of size

n

n \geq 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

Which one of the following graphs is NOT planar?

G

be a simple graph with

20

100

edges. The size of the minimum vertex cover of G is

8

. Then, the size of the maximum independent set of

G

G

be a simple connected planar graph with

13

19

edges. Then, the number of faces in the planar embedding of the graph is:

G_1=(V,E_1)

G_2 =(V,E_2)

be connected graphs on the same vertex set

V

with more than two vertices. If

G_1 \cap G_2= (V,E_1\cap E_2)

is not a connected graph, then the graph

G_1\cup G_2=(V,E_1\cup E_2)

How many graphs on

n

labeled vertices exist which have at least

\frac{(n^2 - 3n)}{ 2}

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

G=(V,E)

\mid E \mid \leq 3 \mid V \mid - 6

. The min-degree of

G

\min_{v\in V}\left\{ \text{degree }(v)\right \}

. Therefore, min-degree of

G

How many perfect matching are there in a complete graph of

6

\text{G}

be an arbitrary graph with

n

k

components. If a vertex is removed from

\text{G}

, the number of components in the resultant graph must necessarily lie down between

The maximum number of edges in a

n

-node undirected graph without self loops is

The minimum number of colours required to colour the vertices of a cycle with

n

nodes in such a way that no two adjacent nodes have the same colour is

How many undirected graphs (not necessarily connected) can be constructed out of a given set

V=\{v_1, v_2, \dots v_n\}

n

The number of articulation points of the following graph is