1
$\begingroup$

Suppose $G$ is a simple graph and $V(G)=V(C)\bigcup \{u_1,...,u_n\}$,where $C$ is a $2n$-cycle in $G$ and $V(C)=\{a_1,...,a_n,b_1,...,b_n\}$ such that

$(1)V(C)\bigcap \{u_1,...,u_n\}=\varnothing$;

$(2)E(G)=\{a_1u_1,u_1b_1,a_2u_2,u_2b_2,...,a_nu_n,u_nb_n\}\bigcup E(C)$.

I think there must exists a proper subset $S$ of $\{u_1,...,u_n\}$ such that $G-S$ is a Hamiltonian graph,is it ture?

$\endgroup$

2 Answers 2

2
$\begingroup$

The conjecture is right.It is equivalent to the claim below:

Let G be a simple graph which is a $2n$-cycle equipped with $n$ chords such that $G$ is $3$-regular,in other words,the set of the $n$ chords is a perfect matching of $G$(that is,every vertex of $G$ is matched).Then there must exist at least two different $2n$-cycles in $G$.

The proof is given by Tony Huynh,see my another question:Does this graph contain at least two Hamiltonian cycles?.

$\endgroup$
3
  • $\begingroup$ So, what's that second cycle in my example? $\endgroup$
    – fedja
    Oct 26, 2013 at 2:33
  • $\begingroup$ $a_1$-$a_2$-$u_2$-$b_2$-$b_3$-$u_3$-$a_3$-$a_8$-$u_8$-$b_8$-$b_6$-$b_5$-$b_4$-$u_4$-$a_4$-$a_5$-$a_6$-$a_7$-$u_7$-$b_7$-$b_1$-$u_1$-$a_1$-,so $G-\{u_5,u_6\}$ is a Hamiltonian graph. $\endgroup$
    – user40096
    Oct 26, 2013 at 4:46
  • $\begingroup$ Indeed. Ok, I'll delete my "non-answer" then :-). $\endgroup$
    – fedja
    Oct 27, 2013 at 17:43
1
$\begingroup$

Here $C_{2n}$ is a cycle of length $2n$ s.t. $V(C_{2n})=\{a_1,...,a_n,b_1,...,b_n\}$,where $a_i$ adjacent to $a_{i+1}$,$b_i$ adjacent to $b_{i+1}$ (for $ 1 \leq i <n $) and $a_1$ adjacent to $b_n$,$a_n$ adjacent to $b_1$.Take $S$ =$\{u_2,...,u_{n-1}\}$. Then $V(G-S)=\{a_1,...,a_n,b_1,...,b_n,u_1,u_n\}$ and $E(G-S)=\{a_1u_1,u_1b_1,a_nu_n,u_nb_n\}\bigcup E(C_{2n})$.A Hamiltonian cycle: $a_nu_nb_nb_{n-1}...b_1u_1a_1a_2...a_{n-1}a_n$.So $G-S$ is a Hamiltonian graph.

$\endgroup$
6
  • $\begingroup$ You do not know the edges except they form a cycle (the enumeration $a_j,b_j$ has nothing to do with the cycle order). $\endgroup$
    – fedja
    Oct 22, 2013 at 11:43
  • $\begingroup$ fedja,Thank you for your explaining! $\endgroup$
    – user40096
    Oct 22, 2013 at 11:49
  • $\begingroup$ So u want to say in the cycle $C$ $a_1$ adjacent to $b_2$ and $b_n$? $\endgroup$
    – jon
    Oct 22, 2013 at 11:49
  • $\begingroup$ No,I just want to say the set of vertices of $C$ is $\{a_1,...,a_n,b_1,...b_n\}$. $\endgroup$
    – user40096
    Oct 22, 2013 at 12:28
  • $\begingroup$ but u should have to know a well-order(@ adjacentcy of the vertices of $C$),then u can find a Hamiltonian cycle. In above ans : without loss of generality I had define the edges of the graph $C$ and then we show that $G-S$ is a Hamiltonian graph.So in general u can also claim that. $\endgroup$
    – jon
    Oct 22, 2013 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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