Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I think that in the last part of the argument you actually use that $x_i, x_i'$ are not $x,y$, and potentially their successors. You should check if $x_i, x_i' \in \{ x,y, x', y'\}$ leads to any issue, and if it does you need to refine your pigeonhole principle argument. –  N. S. Oct 13 '12 at 18:34
    
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! –  user42693 Oct 13 '12 at 18:52
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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