Suppose E is a set of non adjacent edges of G and $\delta(G)\ge\frac{n+e}{2}$.Show that there is a Hamiltonian cycle that contains all the edges of E.

Question

Suppose that $E$ is a set of non adjacent edges of graph $G$ that $\delta(G) \ge \frac{n+e}{2}$ where $|E|=e$. Show that there is a Hamiltonian cycle that contains the edges of $E$.

I know that if the degree of each vertex of a graph is greater than or equal to $n/2$ it has a Hamiltonian cycle. $\delta(G)$ is the least degree of vertices of $G$. So $G$ has a Hamiltonian cycle. But I don't know how to show that this cycle contains the edges of $E$. Would someone please help?

Answer 1

I will try to give a proof of this fact. The proof will be done by induction on the number $e$. If $e=0$, our statement follows from Dirac's theorem. Let $e>0$, edge $uv\in E$ and $E'=E-uv$. By induction there exists a Hamiltonian cycle of $G$ containing all edges of $E'$. If edge $uv$ belongs to this cycle, then our assertion is proved.

Let it not be so (see Figure 1, Figure 1 shows the Hamiltonian cycle of $G$ as a circle and edge $uv$ its chord). We consider a simple path $x\ldots uv\ldots y$ that passes through all vertices of graph $G$. This simple path contains all edges from $E$, since the edges from $E$ are pairwise non-adjacent and $xv, yu\notin E$. If $x$ and $y$ are adjacent, we obtain a Hamiltonian cycle of $G$ containing all edges from $E$.

Let $x$ and $y$ be non-adjacent. Let us sequentially number from left to right all vertices of this path as follows: $x_1=x,\ldots,x_n=y$. Let $I_1=\{i\mid x_i\sim y\}$ and $I_2=\{i\mid x\sim x_{i+1}\}$; $p\sim q$ means that $pq$ is an edge of our graph. By the assumption $|I_1|\geq(n+e)/2$ and $|I_2|\geq(n+e)/2$. In addition, since $x$ and $y$ are not adjacent, then $x,y\notin I_1\cup I_2$ and so $|I_1\cup I_2|\leq n-2$. It follows that $|I_1\cap I_2|\geq e+2$. Hence, there exists $i\in I_1\cap I_2$ such that $x_i$ is not the left end of any edge of $E$. Since $i\in I_1$, then $x_i\sim y=x_n$ and since $i\in I_2$, then $x_{i+1}\sim x=x_1$. As a result, we obtain a Hamiltonian cycle (see Figure 2): $$ x_1\ldots x_ix_n\ldots x_{i+1}x_1. $$