0
$\begingroup$

I am asked to prove that every connected, bipartite, k-regular ($k \ge2$) graph is 2-connected. Now for $n \ge 3$ I can use few of the theorems included and show that it is so indeed (focusing on the fact that the graph is bipartite).

What I wonder/have issue with is - what if we take a graph with two vertices x,y that have multiple edges between them? It would be 1-connected according to my book's definition (the connectivity of G is the minimum size of vertex set S such that G-S is disconnected or has only one vertex). What am I missing in here?

Connected question: A connected k-regular bipartite graph is 2-connected.

Edit: To clarify, my definition of graph allows multiple edges and loops. If a graph has none of these, it's stated it is a simple graph. In this question it isn't stated that the graph is a simple graph.

$\endgroup$
  • $\begingroup$ Normally the definition of graph does not allow more than one edge between any two vertices. What is your definition of graph? $\endgroup$ – Seth May 8 '14 at 22:22
  • $\begingroup$ Graphs having multiple edges are called multigraphs and behave differently than ordinary graphs. If the problem formulation (or the context) does not tell you otherwise, you can assume that there is at most one edge between any two vertices. $\endgroup$ – dtldarek May 8 '14 at 22:26
  • $\begingroup$ Odd, as usually it is stated that a graph is 'simple' if it has no loops or multiple edges. In this question it isn't stated. It has to be though for the claim to uphold? $\endgroup$ – Studentmath May 8 '14 at 22:36
1
$\begingroup$

Suppose your $k$-regular graph $G$, split in vertex parts $X$ and $Y$, is not 2-connected.
Then there is a vertex $v$ whose removal splits $G$ in at least two connected components. Let $C$ be one of these components.

We'll just count the number of edges in $C$ and run into a problem. Suppose without loss of generality that $v \in Y$. Now, $C$ induces a bipartite graph, say with parts $X' \subset X$ and $Y' \subset Y$. Let $x = |X'|$ and $y = |Y'|$. Also, let $i$ be the number of edges going from $v$ to $C$. We have that $0 < i < k$. It turns out the bounds on $i$ are important, but I'll let you figure out why exactly we must have that.

Let $e_C$ be the number of edges in $C$. We have $e_C = x \cdot k - i$, since every vertex in $X'$ is of degree $k$, but the edges going to $v$ are not in $C$. Also, $e_C = y \cdot k$, since $Y'$ has no edges going out of $C$. Therefore $x \cdot k - i = y \cdot k$ and thus $x - \frac{i}{k} = y$. Since $y$ is the number of vertices in $Y'$, it is an integer, meaning that $i$ is a multiple of $k$. But $0 < i < k$, which makes it impossible.

Note that we never assumed $G$ was a simple graph, and this holds even if we have multi-edges.

EDIT : I seem to have missed the point of the question, as commented. The specific problem at hand is when $n = 2$. It does look there there are problems in the statement, and that you need n>2. Every definition of vertex-connectivity I came across states that a complete graph of n vertices has connectedness n−1 (even when extended to multigraphs). So the graph you speak would not be 2-connected. I think it's a mistake, and this happens sometimes in the literature with the special cases that are considered 'trivial'.

$\endgroup$
  • $\begingroup$ We didn't assume in any place that G was a simple graph, but your proof relies on the fact the cut-vertex may split it into at least two connected components. That would be true for $n\ge 3$, but not for n=2. For n=2 a cut vertex will simply leave an isolated vertex, according to my definitions. See my issue with it? $\endgroup$ – Studentmath May 9 '14 at 16:51
  • 1
    $\begingroup$ Ah I'm sorry, I seem to have missed your point. It does look there there are problems in the statement, and that you need $n > 2$. Every definition of vertex-connectivity I came across states that a complete graph of $n$ vertices has connectedness $n - 1$ (even when extended to multigraphs). So the graph you speak would not be $2$-connected. I think it's a mistake, and this happens sometimes in the litterature with the special cases that are considered 'trivial'. $\endgroup$ – Manuel Lafond May 9 '14 at 17:52
  • $\begingroup$ Thank you, I have reached the same conclusion. If you could edit it into your question I will choose it as the answer. $\endgroup$ – Studentmath May 9 '14 at 17:58
  • $\begingroup$ I have done so, but maybe you'd like to wait before like 1 day, just in case someone has a better explanation. Your call :) $\endgroup$ – Manuel Lafond May 9 '14 at 18:06

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.