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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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?.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, what's that second cycle in my example? $\endgroup$
    – fedja
    Commented 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
    Commented Oct 26, 2013 at 4:46
  • $\begingroup$ Indeed. Ok, I'll delete my "non-answer" then :-). $\endgroup$
    – fedja
    Commented 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.

Improve this answer
$\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
    Commented Oct 22, 2013 at 11:43
  • $\begingroup$ fedja,Thank you for your explaining! $\endgroup$
    – user40096
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 22, 2013 at 13:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .