1
$\begingroup$

Given an integer $k>1$, is there a connected bipartite graph $\Gamma = (A, B, E)$ where $A\cap B = \emptyset$ and $E \subseteq \big\{\{a, b\}:a\in A, b\in B\big\}$ such that

  1. $|A| = |B|$,
  2. $\text{deg}(v) \geq k$ for all $v\in A\cup B$, and
  3. there is no Hamiltonian path in $\Gamma$

?

$\endgroup$
1
  • 1
    $\begingroup$ Yes. A family of examples for $k=2$ could be constructed as follows. Take two even cycles, and on both select a pair of non-adjacent vertices $u,v$ and $u',v'$ such that both distances are of the same-parity. Connect both cycles by two edges $uu'$ and $vv'$, and subdivide both mentioned edges. If you feel it's instructive, I can expand this into an answer and draw some examples... $\endgroup$ Sep 1, 2017 at 7:16

2 Answers 2

4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Very nice construction and drawing, thanks! $\endgroup$ Sep 1, 2017 at 8:08
5
$\begingroup$

Take any $k\ge 1$ and four disjoint sets of vertices $A,B,C,D$ with $|A|=|D|=k+2$, $|B|=|C|=k$. Completely join $A$ to $B$, $B$ to $C$ and $C$ to $D$. This gives a bipartite graph of minimum degree $k$ with no hamiltonian path. (Proof: Consider how a hamiltonian path can choose edges between $A$ and $B$.)

$\endgroup$
1
  • 2
    $\begingroup$ That's a very nice answer! $\endgroup$ Sep 1, 2017 at 10:05

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.