GATE CS 2014 Set 1 Q52 — Graphs: Connectivity, Matching, Colouring

We can determine if a degree sequence is graphic using either basic graph properties or the Havel-Hakimi theorem.

Method 1: Intuitive Analysis

Let's analyze option C: $(3, 3, 3, 1, 0, 0)$.

• There are $6$ vertices in total.
• Two vertices have a degree of $0$, meaning they are completely isolated and have no edges connected to them.
• This leaves only $4$ active vertices to accommodate the remaining degrees: $(3, 3, 3, 1)$.
• In a simple graph with $4$ vertices, the maximum possible degree of any vertex is $4 - 1 = 3$.
• If three vertices have a degree of $3$, each of them must be connected to all other $3$ vertices in this $4$-vertex subgraph.
• If three vertices are connected to every other vertex, then every vertex in this subgraph must have a degree of at least $3$.
• However, the fourth vertex has a degree of only $1$, which is a contradiction.

Thus, the sequence $(3, 3, 3, 1, 0, 0)$ is NOT graphic.

Method 2: Havel-Hakimi Theorem

The Havel-Hakimi algorithm recursively reduces a degree sequence to determine if it is graphic:

1. Sort the sequence in non-increasing order.
2. Remove the first element (say, $d$) and subtract $1$ from the next $d$ elements.
3. If any element becomes negative, the sequence is not graphic. If all elements become $0$, it is graphic.

Applying this to Option C: $(3, 3, 3, 1, 0, 0)$

• Remove $3$, and subtract $1$ from the next $3$ elements: $$(3-1, 3-1, 1-1, 0, 0) \implies (2, 2, 0, 0, 0)$$
• Remove $2$, and subtract $1$ from the next $2$ elements: $$(2-1, 0-1, 0, 0) \implies (1, -1, 0, 0)$$

Since we obtained a negative degree ($-1$), the sequence is not graphic.