Skip to main content
added 1 character in body
Source Link

The answer is yes. One may construct a family of examples of $\Gamma$ with the minimal degree degree equal to $2$, as follows.

  • For even integers $a$ and $b$, start with two even cycles $C_a$ and $C_b$.
  • On cycles $C_a$ and $C_b$, select pairs of non-adjacent vertices $u,v$ and $u′,v′$, respectively, such that both distances are of the same-parity.
  • Connect both cycles by two edges $uu′$ and $vv′$.
  • Subdivide both mentioned edges $uu′$ and $vv′$ by vertices $u^*$ and $v^*$, respectively.

First notice that if there exists a Hamiltonian path in $\Gamma$, call it $P=p_1,\dots,p_{a+b+2}$, it may not start/end with $u^*$ or $v^*$. Indeed, wlog. suppose $p_1=v^*$ and $p_2=v$, and notice that if in $C_a$, our path $P$ covers both (non-trivial) paths from $v$ to $u$ in $C_a$, then $C_b \cup P=\emptyset$, a contradiction.

We may hence, wlog., assume that $p_1$ and $p_{a+b+2}$ both lie in $C_a$. So take now a sub-sequence $P'=P\cap C_b$ and notice that $P'$ corresponds to a Hamiltonian path in $C_b$, with endpoints in $u'$ and $v'$. Since $d_{C_b}(u',v')>1$, this is a contradiction.

A small example with $a=b=4$ is drawn below. (can someone tell me how to make it look smaller?)

enter image description here

The answer is yes. One may construct a family of examples of $\Gamma$ with the minimal degree equal to $2$, as follows.

  • For even integers $a$ and $b$, start with two even cycles $C_a$ and $C_b$.
  • On cycles $C_a$ and $C_b$, select pairs of non-adjacent vertices $u,v$ and $u′,v′$, respectively, such that both distances are of the same-parity.
  • Connect both cycles by two edges $uu′$ and $vv′$.
  • Subdivide both mentioned edges $uu′$ and $vv′$ by vertices $u^*$ and $v^*$, respectively.

First notice that if there exists a Hamiltonian path in $\Gamma$, call it $P=p_1,\dots,p_{a+b+2}$, it may not start/end with $u^*$ or $v^*$. Indeed, wlog. suppose $p_1=v^*$ and $p_2=v$, and notice that if in $C_a$, our path $P$ covers both (non-trivial) paths from $v$ to $u$, then $C_b \cup P=\emptyset$, a contradiction.

We may hence, wlog., assume that $p_1$ and $p_{a+b+2}$ both lie in $C_a$. So take now a sub-sequence $P'=P\cap C_b$ and notice that $P'$ corresponds to a Hamiltonian path in $C_b$, with endpoints in $u'$ and $v'$. Since $d_{C_b}(u',v')>1$, this is a contradiction.

A small example with $a=b=4$ is drawn below. (can someone tell me how to make it look smaller?)

enter image description here

The answer is yes. One may construct a family of examples of $\Gamma$ with the minimal degree equal to $2$, as follows.

  • For even integers $a$ and $b$, start with two even cycles $C_a$ and $C_b$.
  • On cycles $C_a$ and $C_b$, select pairs of non-adjacent vertices $u,v$ and $u′,v′$, respectively, such that both distances are of the same-parity.
  • Connect both cycles by two edges $uu′$ and $vv′$.
  • Subdivide both mentioned edges $uu′$ and $vv′$ by vertices $u^*$ and $v^*$, respectively.

First notice that if there exists a Hamiltonian path in $\Gamma$, call it $P=p_1,\dots,p_{a+b+2}$, it may not start/end with $u^*$ or $v^*$. Indeed, wlog. suppose $p_1=v^*$ and $p_2=v$, and notice that if our path $P$ covers both (non-trivial) paths from $v$ to $u$ in $C_a$, then $C_b \cup P=\emptyset$, a contradiction.

We may hence, wlog., assume that $p_1$ and $p_{a+b+2}$ both lie in $C_a$. So take now a sub-sequence $P'=P\cap C_b$ and notice that $P'$ corresponds to a Hamiltonian path in $C_b$, with endpoints in $u'$ and $v'$. Since $d_{C_b}(u',v')>1$, this is a contradiction.

A small example with $a=b=4$ is drawn below. (can someone tell me how to make it look smaller?)

enter image description here

Source Link

The answer is yes. One may construct a family of examples of $\Gamma$ with the minimal degree equal to $2$, as follows.

  • For even integers $a$ and $b$, start with two even cycles $C_a$ and $C_b$.
  • On cycles $C_a$ and $C_b$, select pairs of non-adjacent vertices $u,v$ and $u′,v′$, respectively, such that both distances are of the same-parity.
  • Connect both cycles by two edges $uu′$ and $vv′$.
  • Subdivide both mentioned edges $uu′$ and $vv′$ by vertices $u^*$ and $v^*$, respectively.

First notice that if there exists a Hamiltonian path in $\Gamma$, call it $P=p_1,\dots,p_{a+b+2}$, it may not start/end with $u^*$ or $v^*$. Indeed, wlog. suppose $p_1=v^*$ and $p_2=v$, and notice that if in $C_a$, our path $P$ covers both (non-trivial) paths from $v$ to $u$, then $C_b \cup P=\emptyset$, a contradiction.

We may hence, wlog., assume that $p_1$ and $p_{a+b+2}$ both lie in $C_a$. So take now a sub-sequence $P'=P\cap C_b$ and notice that $P'$ corresponds to a Hamiltonian path in $C_b$, with endpoints in $u'$ and $v'$. Since $d_{C_b}(u',v')>1$, this is a contradiction.

A small example with $a=b=4$ is drawn below. (can someone tell me how to make it look smaller?)

enter image description here