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

Answer 2

You can show this by being a bit more careful in the proof of Dirac's theorem. I will use $E_0$ to denote your $E$ so that we don't confuse it with the edge set of the graph.

Let $P = p_1,\ldots,p_k$ be a path that contains the most edges from $E_0$ and one that is longest among such paths. We first construct a cycle on the vertices $p_1,\ldots,p_k$ with the same number of edges from $E_0$ as $P$. In order to do this, we show that there is an index $1 \leq i < k$ such that (1) $p_1p_{i+1}$ is an edge, (2) $p_ip_k$ is an edge, and (3) $p_ip_{i+1}$ is not in $E$.

This is almost the same as in the usual proof for Dirac's theorem. First, every neighbour of $p_1$ is on $P$, since otherwise we could simply extend $P$ to get a longer path; and similarly for $p_k$. Let $A$ denote the vertices $p_l, 1 \leq l < k$ of $P$ for which $p_{l+1}$ is a neighbour of $p_1$ and $p_lp_{l+1}$ is not in $E_0$. Let $B$ denote the neighbours of $p_k$. Then $A$ and $B$ are not disjoint, for otherwise $P$ would contain at least $$\deg(p_1) - e + \deg(p_k) + 1 \geq n+1$$ vertices (the $+1$ comes from the fact that $p_k$ is not in $A \cup B$). So there is a vertex $p_i \in A \cap B$, and this vertex clearly satisfies (1),(2) and (3).

Consider the cycle $C = p_1,p_{i+1},p_{i+2},\ldots,p_k,p_i,p_{i-1},\ldots,p_1$. Note that $C$ contains at least as many edges from $E_0$ as $P$. Now we are almost done; we just have to show that $C$ is a Hamiltonian cycle containing every edge of $E_0$. The following is a bit messy but if you draw it on a paper then it should be clear what's going on. This is the part where we shall use the assumption that the edges in $E_0$ are disjoint.

First, suppose for contradiction that $C$ is not a Hamiltonian cycle. This implies that there is some outgoing edge $pv$ from $C$ (you should verify that $G$ is connected). At most one edge in $E_0$ is incident to $p$, so we can take an edge $pu \in E(C) - E_0$. But then the path starting with $v,p,u$ and going around $C$ is longer than $P$ and contains at least as many edges from $E_0$, contradicting the choice of $P$. So $C$ is a Hamiltonian cycle. It also contains every edge from $E_0$: suppose for contradiction that there is some edge $uv \in E_0 - E(C)$, and let $u = q_1,q_2,\ldots,q_i = v,q_{i+1},\ldots,q_n = u$ be a cyclic ordering of $C$. Note that $q_1q_2$ and $q_iq_{i+1}$ are not in $E_0$. Then $q_2,\ldots,q_i,q_1,q_{n-1},\ldots,q_{i+1}$ is a Hamiltonian path that contains more edges from $E_0$ than $P$, a contradiction.