quick question on showing every edge in a graph of minimum degree n+1 is contained in a hamiltonian circuit. 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. 
 A: 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.
A: Let $xy$ be an edge, and pick a longest path $P$ containing the edge $xy$, call the endpoints $u$ and $v$.

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):

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.
