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

2.8k Views Asked by At

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

There are 2 best solutions below

2
On BEST ANSWER

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| $$

0
On

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

enter image description here