0

Can anyone give me an example of a Hamiltonian graph $H$ of order $n=2k$ for some $k\geq 2$ where $k$ vertices have degree $2$, no two vertices of which are adjacent, while the remaining vertices have degree $3$ or more?

Does this question needs a generic example. I can think of only specific ones?

flonk
  • 2,434
user109260
  • 101
  • 1

1 Answers1

1

First, by Handshaking Lemma, $k$ must be even.

Pick any $k$ even, and draw a cycle $C_{2k}$. For simplicity label the vertices $1,2,3,.., 2k$. Now since $k$ is even, there is an even number of vertices in $\{1,3,5,.., 2k-1\}$. Split them in $\frac{k}{2}$ pairs in any way you want. Add those pairs as edges.

For example, if $k=2$ you have the graph

$$V=\{ 1,2,3,4 \}$$ $$E=\{ (1,2), (2,3), (3,4), (4,1), (1,3) \}$$

This is just $K_4$ without one edge.

N. S.
  • 132,525
  • 1
    Actually you don't need $k$ to be even; the remaining vertices don't have to have degree exactly $3$. For general $k$, instead of connecting the vertices in ${1,3,5,\ldots,2k-1}$ pairwise, just create a cycle passing through each of those vertices. – Kevin Ventullo Nov 16 '13 at 23:55