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.