# Can the degree sequence $2,2,2,2,2,3,3$ be Hamiltonian graph, if not can it be a simple graph?

If $G$ is a simple graph of $7$ vertices whose vertex degrees are $2,2,2,2,2,3,3$ is it Hamiltonian graph? Does a simple non-Hamiltonian graph exist with $7$ vertices whose vertex degrees are $2,2,2,2,2,3,3$?

The only comprehensive way to determine whether a graph is Hamiltonian that I found is the Bondy-Chvatal theorem. According to this theorem let $d_i$ be the degree of vertex $v_i\in V$.

Then: $$d_1=2>1\\d_2=2\le2 \quad\land\quad d_{7-2=5}=2<5$$ therefore according to the above theorem the graph is not Hamiltonian.

But the second question asks if any simple graph exists with such a sequence. But according to the Handshaking lemma: $$\sum_{v\in V}\deg(v)=2\cdot |E|\implies |E|=16/2=8.$$ But isn't it that in any simple graph the number of vertices is always greater than the number of edges? If yes then our graph doesn't exist because it has $8$ edges but $7$ vertices.

I feel there's some catch in the question because if my answer to second part is correct than why would I be asked if such a Hamiltonian graph exists if the graph itself is not possible?

Also I have a micro-subquestion on the Bondy-Chvatal theorem which says that for degree sequence $d_1\le d_2\le ...\le d_n$ if no $m<n/2$ exists such that $d_m\le m$ and $d_{n-m}<n-m$ then Hamiltonian graph is possible. What if $n$ is odd? Is $m=\lceil n/2 \rceil$ then?

## 2 Answers

Consider a cycle on 7 vertices with one additional "chord-like" edge. You get a simple graph with the desired degree sequence.

Your statement

in any simple graph the number of vertices is always greater than the number of edges

is faulty, since a complete graph on $n>1$ vertices has $$|E| = \frac{n(n-1)}{2} > n = |V|$$

• But can the sequence be Hamiltonian at all? In other words is my conclusion from Bondy-Chvatal correct? – Yos May 18 '18 at 15:46
• @Yos yes, it is not Hamiltonian, it seems – gt6989b May 18 '18 at 15:47

The following graph has vertex degree $2,2,2,2,2,3,3$ but does not have a Hamiltonian cycle. 