Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been struggling with this exercise; all ideas have been unfruitful, leading to dead ends. It is from Balakrishnan's A Textbook of Graph Theory, in the connectivity chapter:

Prove that a connected k-regular bipartite graph is 2-connected.

(That is, deletion of one vertex alone is not enough to disconnect the graph).

I think the objective is to make use of Whitney's theorem according to which a graph (with at least 3 vertices) is 2-connected iff any two of its vertices are connected by at least two internally disjoint paths. But I'll welcome any ideas or solutions.

Thank you!

share|improve this question
    
Is there some hypothesis on $k$. What about the graph with 2 vertices and 1 edge? –  Sigur Jul 27 '12 at 13:24
1  
@Sigur That one is 2-connected. –  Weltschmerz Jul 27 '12 at 13:29

2 Answers 2

up vote 4 down vote accepted

Let $G = (V_{1}\cup V_{2},E)$ be a connected, $k$-regular bipartite graph where $V_{1}$ and $V_{2}$ are the partite vertex sets. As the case $k=1$ is trivial, we may assume that $k \geq 2$ and therefore $|V_{1}\cup V_{2}|\geq 4$.

Assume for contradiction that $G$ is not $2$-connected.

As $G$ is connected but not $2$-connected, there exists a vertex $v$ whose removal disconnects the graph. Without loss of generality we may assume that $v \in V_{1}$. Then $G-v = \uplus_{i\in [1,a]} G_{i}$ where each $G_{i}$ is a connected component and $a \geq 2$.

As $a \geq 2$, there exists some component $G_{b}$ such that $|V_{1}\cap V(G_{b})| \geq |V_{2}\cap V(G_{b})|$. (It shouldn't be too hard to convince yourself of this) For convenience denote $L = V_{1}\cap V(G_{b})$ and $R = V_{2}\cap V(G_{b})$.

As $G_{b}$ is a connected component and $G$ was connected, and $v \in V_{1}$, at least one vertex in $R$ was adjacent to $v$, and therefore has degree less than $k$. However the vertices in $L$ have lost no edges Then we have $$ \sum_{u\in R}deg(u) < k\cdot|R| < k\cdot|L| = \sum_{w \in L}deg(w) $$ However as $G[L \cup R]$ forms a bipartite graph, we know $$ \sum_{u\in R}deg(u) = \sum_{w \in L}deg(w) $$

Thus we have a contradiction, so $G$ must be at least $2$-connected.

share|improve this answer
    
I'm not sure about the last equality. Why is it so? It seems that in the inequality you're considering degrees in $G-v$, but in the equality, degrees in $G$. –  Weltschmerz Jul 28 '12 at 22:55
1  
The vertex sets $L$ and $R$ form a connected component after the removal of $v$, and of course this component is still bipartite. So all the edges of $L$-vertices have their endpoint within the connected component, but outside of $L$, so they must end in $R$ and vice versa. Thus every edge in $G[L\cup R]$ has an endpoint in $L$ and an endpoint $R$, so the degree on one side is the same as the other. –  Luke Mathieson Jul 29 '12 at 0:20

Proof by contradiction. Suppose $v$ is a cut vertex of $G = G(X,Y).$ Without loss of generality, let $v\in Y.$ Then $G-v$ has at least two components, say $C_1$ and $C_2.$ Let $(X_1,X_2)$ be the bipartition of $C_1.$ Let $s$ be the number of neighbors of the vertex $v$ in $C_1$ (that is, in $X_1$), then $s<r.$

Since $C_1$ is bipartite, the number of edges incident at $Y_1$ in $C_1$ must be equal to the number of edges incident at $X_1$ in $C_1.$ Hence $$ r|Y_1| = s(r-1) + (|X_1| - s)r$$ $$\Rightarrow s = (|X_1| - |Y_1|)r$$ $$\Rightarrow s \geq r,$$ a contradiction.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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