A question about connected regular bipartite graph

bipartite-graphscombinatoricsgraph theory

Let $G = (V = V_1 \cup V_2,E)$ be a connected regular bipartite graph of degree $n+1$ with vertex sets $V_1$ and $V_2$ of size $|S|$.

If we choose $|S|$ vertices from $V$ with at least one vertex each from $V_1$ and $V_2$ (call this set $S$), can we show that there are two vertices in $S$ that are neighbors?

What I've done so far:

I tried to get a contradiction by considering the possibility $S$ has no vertices that are neighbors, but I could not make much progress. In my working, I tried to get a contradiction with respect to the connectedness of the group. The crux of my idea was to show that bipartition of vertices is not unique and it looked so natural, however there seems to be a small flaw in my argument. It's not fully complete.

It'd be really helpful if I get an hint.

Thank you!

Best Answer

I am not certain if I misunderstood the question but I fail to find counterexample for $n=2$ mentioned by kabenyuk. This is my attempt at a proof by contradiction:

Let's assume there exists such a set $S$ without any edges and $|V_1| = |V_2| = |S|$.

Let's consider:

  • $C_1$ as vertices in both $V_1$ and $S$,
  • $C_2$ as vertices in both $V_2$ and $S$,
  • $L_1$ as vertices in $V_1$ and not in $S$, and
  • $L_2$ as vertices in $V_2$ and not in $S$.

We can see that: $$0 <|C_1|=|S|-|C_2|=|V_2|-|C_2|=|L_2|$$ and similarly $0 <|C_2|=|L_1|$.

Because we assume that there are no edges between vertices of $C_1$ and $C_2$, all edges from $C_1$ must go to $L_2$: by assumption about $S$ and because the graph is bipartite.

That means all edges from $L_2$ must go to $C_1$, because the graph is regular and $|C_1|=|L_2|$.

That means the graph is not connected as there are no edges between $C_1 \cup L_2$ and $L_1 \cup C_2$, $|L_2|=|C_1|>0$, and $|L_1|=|C_2|>0$. This is a contradiction as the graph is connected. That means that either no such graph exists or each set $S$ must have at least one edge.

Related Question