1
$\begingroup$

Suppose $G$ is a simple graph with order $n$, the minimum degree $\delta\geq \frac{n+q}{2}$, prove that for any pairwise non-adjacent $q$ edges, there exists a Hamiltonian cycle $H$ contains these edges.


I want to choose a Hamiltonian cycle $H'$ contains these edges as much as possible, then define $S$ and $T$ such that $$n+q\leq d(u)+d(v)=|S|+|T|=|S \cup T|+|S\cap T|\leq n+q-1$$ to induce contradiction, but I don't know how to define $S$ and $T$, could anyone help me?

$\endgroup$
1
$\begingroup$

Contract all $q$ edges to get $G’$. $G’$ has order $n-q$ and minimum degree $\delta ‘ \geq \frac{n-q}{2}$ since it cannot decrease more than the order did. Since the minimum degree is at lest half the order, $G’$ is Hamiltonian as proven by Dirac.

$\endgroup$
1
  • $\begingroup$ Thanks, the idea is amazing! $\endgroup$
    – Xin Fu
    Mar 20 '19 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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