1
$\begingroup$

Although this seems rather obvious, I couldn't prove it rigorously. Any ideas how to prove it? The graph is assumed to be simple and connected.

Explanation of the terms:

  • $k$-regular means that all vertices have degree $k$;
  • bipartite means that there are 2 sets of vertices $X, Y$, where vertices from $X$ only have edges with vertices $Y$ and vertices from $Y$ only have edges with vertices from $X$;
  • cut-edge is an edge which removal disconnects the graph;

This is b) part of the exercise, maybe a) part can help:

a) If all vertices $v \in G$ have an even degree, $G$ does not have cut-edge

From a) it actually follows that for even $k$, b) is true, thus only case with odd $k$ left to prove.

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby Oct 29 '13 at 10:57
  • $\begingroup$ Yes, the graph is connected. I was considering several ways of prooving, I can sketch one of them. Delete an edge $e$, remember its endpoints $x, y$. If $e$ was cut-edge, then in $G-e$ there is no path between $x, y$. Suppose $x$ is connected with vertices from set $X_1$, $y$ from set $Y_1$. Sets $X_1$ and $Y_1$ can't have common edges, as otherwise we have a path between $x$ and $y$. However, set $X_1$ must have neighs other then $x$ (since $k$>1), label this set $X_2$. The problem is that $X_2$ is of uncertain size. I can show that $X_3$ has at least one element, but furhter I am stuck. $\endgroup$ – MindaugasK Oct 29 '13 at 13:13
  • $\begingroup$ Another way of prooving the exercise would be to show that $k$-regular bipartite graph has $2$-regular bipartite graph as a subraph or $k-1$-regular bipartite graph as a subgraph, but I could not come up with an algorithm to delete edges properly (I am nearly sure the algorithm I was thinking about should actually work, but I can't see more than 3-4 steps (edge deletions) ahead) $\endgroup$ – MindaugasK Oct 29 '13 at 13:22
4
$\begingroup$

Ok, here is a simple proof I came up by myself. I was apparently going the wrong way in trying to prove the exercise.

Proof. Suppose edge $e$ is a cut-edge. Study graph $G-e$. For any $v \in G-e$ other then $e$ endpoints $x, y$, the vertex degree $d(v) = k$, and $d(x)=d(y)=k-1$.

Now, since graph $G$ is bipartite, graph $G-e$ remains bipartite. Also, because $e$ is a cut-edge, $G-e$ is composed of 2 components $H_1, H_2$, which are also both bipartite, and each contains exactly one of $x, y$. Assume WLG that $H_1$ has vertex $x$, that $H_1$ has vertex bipartition $X_1, Y_1$ and that $x \in X_1$.

Clearly, in subgraph $H_1$, we have

$S_1 = \sum_{v\in X_1 }d(v) = k(|X_1|-1) + k-1$ and $S_2 = \sum_{v\in Y_1 }d(v) = k(|Y_1|)$, and $S_1$ can't be equal $S_2$ unless $k=1$. However, it must be the case that $S_1 = S_2$ in a bipartite graph. Thus, our initial assumption that $e$ is a cut-edge was wrong. Therefore, $G$ has no cut-edge. $\Box$

$\endgroup$
  • $\begingroup$ I like this proof. $\endgroup$ – G. Bach Oct 29 '13 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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