How to draw an undirected graph with nodes of degrees: $2, 2, 2, 2, 2, 1, 1, 1, 1$

Question

I want to draw an undirected connected graph with $9$ nodes, having the degrees:

$$2, 2, 2, 2, 2, 1, 1, 1, 1$$

I know that this graph will have $7$ edges, but how? I am trying each time, I am stopping after node $7$ and if I draw $8$ it is having degree $2$ instead of $1$. Please help.

Answer 1

Suppose such a graph G exists. Then G can not contain a cycle. For, then all the vertices must be of degree 2 or there must be a vertex of degree at least 3 as G is connected. Thus, we are looking for a connected acyclic graph, that is a tree, with 9 vertices and 7 edges. But every tree with 9 vertices must have exactly 8 edges. So such a graph G doesn't exist!

Also, it is worth to remember that a tree is minimally connected. So, to make an $n$ vertex connected graph we need at least $n-1$ edges.

Answer 2

No such graph exists:

Proof 1:

This can be proved with the Havel-Hakimi theorem quite easily:

Iteration $1$:If $2,2,2,2,2,2,2,1,1$ is graphical, so is $1,1,2,2,2,2,1,1=2,2,2,2,1,1,1,1$, this is of total even degree, reapply H-H,

Iteration $2$: $2,2,2,2,1,1,1,1\to 1,1,2,1,1,1,1=2,1,1,1,1,1,1$ this is even, reapply H-H

Iteration $3$: $2,1,1,1,1,1,1\to0,0,1,1,1,1$, this isn't connected, and hence doesn't meet the criteria. Hence no such graph is graphical.

---

Proof 2:

If such a connected graph existed, that joined all vertices(nodes), it would need to have atleast $8$ edges. This means the total degree would need to be $\geq 16$. Here we have a total degree of $14$, which isn't possible.

Even without the $8$ edge observation, we have $4$ vertices with degree $1$, this means the remaining degree is $10$ between the last $5$, this is $2$ each.

If we have $4$ with degree one, we have

Case 1) $4$ vertices to pick, each of them already have degree one

Case 2) $1$ that has degree $0$.

1) If we choose to join any of the $4$ together, they both become degree $2$, and we can do this with any choice, this instantly makes the problem unconnected, as we have $2$ edges to join $3$ disjoint paths.

2) If we connect this to one of our 'to be degree two', we have '$2,1,1,1,1,1,1,1,1$', with three edges to place. This can only leave us with '$2,2,2,2,2,2,2,1,1$'

Hence this cannot occur.

---

Answer 3

But by handshaking lemma, we know that the minimun number of edges required to draw a graph is sum of degrees of vertices/2. In this case also this is happening as sum of degrees of vertces=even. Then also still why we can not have such a graph possible?