3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

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

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

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.