1
$\begingroup$

Show that if every vertex in a graph on $n$ vertices has degree at least $\frac{n+1}{2}$, then every edge $e\in E(G)$ in G is contained in a Hamiltonian circuit.

My battle strategy: We know that there exists a Hamiltonian Circuit $H$ in G. So assume there is some edge $e$=$(x,y)$ in $G$ but not in $H$. Then, choosing an orientation of $H$, we can consider the successors of $x,y$ in $H$, call them $x',y'$. Then the path $P$=$P_1\cup P_2\cup P_3$ defined by $P_1=[x',y]\subset H$, $P_2=(x,y)$, $P_3=[x,y']\subset H$ is an Hamiltonian circuit containing $(x,y)$, providing that $(x',y')$ is in $E(G)$.

If not, then since the degree of each vertex is greater than $\frac{n}{2}$, the pigeonhole principle applied to the sets {$i:x_i$ is adjacent to $y'$} and {$i:x_i'$ is adjacent to $x'$} on the remaining $n-1$ vertices of $G$ implies there exists a pair of vertices $x_i,x_i'$ in $H$ adjacent two these two points. Connecting $x$ to $x_i'$ and $y'$ to $x_i$, and deleting the edge $(x_i', x_i)$ gives a Hamiltonian circuit containing $(x,y)$.

There must be something wrong with my argument at the end - since I've been able to verify with examples that the property isn't necessarily true if you only have deg $\frac{n}{2}$, but $\frac{n+1}{2}$ gives two such pairs, which seems totally unnecessary since you can construct the Hamiltonian circuit with one.

  • 0
    Yep - this was the error. they can't connect to x or y because if they do, the resulting circuit won't be Hamiltonian - since (x,y) has to be in our new circuit. therefore the number of edges from the successors decreases by four, and the number of vertices by two. Then, you need the deg>$\frac{n+1}{2}$ condition to assure that you can still find such a pair of adjacent $x_i,x_i'$ in $H-{x,y}$. Thanks!2012-10-13

2 Answers 2

2

Here is an approach I would try, not sure if it work, but intuitively it should.

Let $e$ be your edge and $u,v$ the two vertices.

Look at $G-\{u\}-\{v\}$. You can prove that this graph is hamiltonian, thus it has an hamiltonian circuit $u_1 \rightarrow u_2 \rightarrow u_3 ... \rightarrow u_{n-2} \rightarrow u_1$.

Now from the condition $\deg(u),\deg(v) \geq \frac{n+1}{2}$, it follows that there are $\frac{n-1}{2}$ edges from $u$ and $v$ to the circuit. Using the pigeonhole principle, you should be able to prove that you can find two consecutive vertices in the circuit so that $u$ is connected to one and $v$ to the other. This allows you to add $u, u$ and the edge to the circuit.

1

Let $xy$ be an edge, and pick a longest path $P$ containing the edge $xy$, call the endpoints $u$ and $v$.

<span class=P">

If $u$ and $v$ are neighbours, then we have a cycle $C$ with the same number of vertices as in $P$. In fact, $C$ must be a Hamilton cycle, otherwise a vertex in $C$ has a neighbour outside of $C$, and $P$ is not a longest path.

We will argue that $u$ has a neighbour $t \neq y$ and $v$ has a neighbour $s \neq x$ such that $s$ and $t$ are neighbours in $P$ and $s$ is closer to $u$ in $P$ than $v$. With knowledge of these edges, we can identify a Hamilton cycle, as depicted below (it's Hamilton for the same reason $C$ is Hamilton above):

Cycle

We know $v$ has at least $\lceil \frac{n+1}{2} \rceil$ neighbours in $P$ (otherwise $P$ is not a longest path). If $u$ has a neighbour to the "right" of one of the neighbours of $v$, excluding $y$, we have found a suitable cycle. There are thus at least $\lceil \frac{n+1}{2} \rceil$ vertices in $P$ that $u$ is not adjacent to (we subtract $1$ for $y$, but add $1$ back again since $u$ cannot be adjacent to itself).

By assumption, $u$ has at least $\lceil \frac{n+1}{2} \rceil$ neighbours in $P$, so, since $P$ has at most $n$ vertices, we must have $n \geq \left\lceil \frac{n+1}{2} \right\rceil+\left\lceil \frac{n+1}{2} \right\rceil$ giving a contradiction. We conclude suitable $s$ and $t$ exist.