Graph Theory


Question 1
Let G be a simple, finite, undirected graph with vertex set \{v_1,...,v_n\}. Let \Delta (G) denote the maximum degree of G and let N=\{1,2,...\} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1,...,n
color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\}
Which of the following statements is/are TRUE?
A
This procedure results in a proper vertex coloring of G.
B
The number of colors used is at most \Delta (G)+1.
C
The number of colors used is at most \Delta (G).
D
The number of colors used is equal to the chromatic number of G.
GATE CSE 2023   Discrete Mathematics
Question 2
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
MSQ
A
The diagonal entries of A^2 are the degrees of the vertices of the graph.
B
If the graph is connected, then none of the entries of A^{n-1}+I_ncan be zero.
C
If the sum of all the elements of A is at most 2(n-1), then the graph must be acyclic.
D
If there is at least a 1 in each of A's rows and columns, then the graph must be connected.
GATE CSE 2022   Discrete Mathematics


Question 3
The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?
MSQ
A
The chromatic number of the graph is 3.
B
The graph has a Hamiltonian path.
C
The following graph is isomorphic to the Peterson graph.

D
The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)
GATE CSE 2022   Discrete Mathematics
Question 4
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
A
A^3
B
A^3 divided by 2
C
A^3 divided by 3
D
A^3 divided by 6
GATE CSE 2022   Discrete Mathematics
Question 5
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .
A
72
B
36
C
16
D
48
GATE CSE 2022   Discrete Mathematics




There are 5 questions to complete.

11 thoughts on “Graph Theory”

Leave a Comment