# 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 1 Explanation:
 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_n$can 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 2 Explanation:

 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 3 Explanation:
 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 4 Explanation:
 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
Question 5 Explanation:

There are 5 questions to complete.

### 11 thoughts on “Graph Theory”

1. Question 6 is of group theory.

• Thank You Abhishek Chavle,
We have updated it.

• Q 11 and 29 too

• Thank You Abhishek Chavle,
We have updated it.

2. Q32, There is a directed edge between vertices R Q., From R to Q.

3. In question number 10 answer is 3, wrong options are given