GATE CS 2017 Set 2 Q23 — Graphs: Connectivity, Matching, Colouring

According to the Handshaking Lemma, the sum of the degrees of all vertices in an undirected graph is equal to twice the number of edges:

Given:

• Number of edges, $|E| = 25$
• The degree of each vertex is at least $3$, i.e., $\text{deg}(v) \ge 3$ for all $v \in V$

Substituting the given values into the Handshaking Lemma:

Since each of the $n$ vertices has a degree of at least $3$:

Combining these two relations:

Since the number of vertices $n$ must be an integer, the maximum possible value of $n$ is $\lfloor 16.67 \rfloor = 16$.

Feasibility Check:
For $n = 16$, the sum of degrees is $50$. We can achieve this with $14$ vertices of degree $3$ and $2$ vertices of degree $4$ ($14 \times 3 + 2 \times 4 = 50$). Such a graph is easily realizable (for example, by starting with a 3-regular graph on 16 vertices which has 24 edges, and adding 1 edge between two non-adjacent vertices).