GATE CS 2003 Q40 — Graphs: Connectivity, Matching, Colouring

To find the constraint on the minimum degree of the graph $G$, we can use the Handshaking Lemma and the given inequality.

Let $d_{\min}$ be the minimum degree of any vertex in $G$, and let $n = |V|$ be the number of vertices. By the definition of minimum degree, we have:

By the Handshaking Lemma, the sum of the degrees of all vertices is equal to twice the number of edges $|E|$:

This gives us a lower bound on the number of edges:

We are given the upper bound on the number of edges:

Combining these two inequalities, we get:

Multiplying both sides by $2$:

Dividing by $n$ (since $n > 0$):

Since $n$ is a positive integer, $\frac{12}{n} > 0$, which strictly implies:

Since the degree of a vertex must be an integer, the maximum possible value for the minimum degree $d_{\min}$ is $5$. Therefore, the minimum degree of $G$ cannot be 6.