Intereting Posts

Least common multiple of sequence of integers
How prove that there are $a,b,c$ such that $a \in A, b \in B, c \in C$ and $a,b,c$ (with approriate order) is a arithmetic sequence?
How to calculate no. of binary strings containg substring “00”?
Variation of Pythagorean triplets: $x^2+y^2 = z^3$
Modularity and prime number sequence
set up a function for the height of the cable above the sea level between the two pylons
LogSine Integral $\int_0^{\pi/3}\ln^n\big(2\sin\frac{\theta}{2}\big)\mathrm d\theta$
Proof by induction regarding injections and part of the pigeonhole principle
Proving quadratic inequalities?
Probability of a zero product given one previous zero product
Improving the inequality $x\sigma_1(x) \leq \sigma_1(x^2)$ for $x \in \mathbb{N}$
Prove that 1+1=2
Characteristic 2
Proving $A \cap C = B \cap C$, but $ A \neq B$
Combinatorics for a 3-d rotating automaton

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).

- Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.
- How can I prove the maximum number of edges?
- permutation group and cycle index question regarding peterson graph
- How many nodes do you need?
- Counting Components via Spectra of Adjacency Matrices
- Two Steps away from the Hamilton Cycle

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!

- How can this technique be applied to a different problem?
- Free Graph Theory Resources
- Looking for a Resource to Identify/Name a Given Graph
- What made the proof of the four color theorem on planes so hard?
- Are all $4$-regular graphs Hamiltonian
- explicit upper bound of TREE(3)
- Showing that a graph has a cycle length less than something
- When a 0-1-matrix with exactly two 1’s on each column and on each row is non-degenerated?
- Free product as automorphism group of graph
- Online tool for making graphs (vertices and edges)?

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.

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.**

- What books are recommended for learning calculus on my own?
- How many non-rational complex numbers $x$ have the property that $x^n$ and $(x+1)^n$ are rational?
- How to think about the change-of-coordinates matrix $P_{\mathcal{C}\leftarrow\mathcal{B}}$
- Likelihood Functon.
- Infinite Cartesian product of countable sets is uncountable
- Finding the values of $n$ for which $\mathbb{F}_{5^{n}}$, the finite field with $5^{n}$ elements, contains a non-trivial $93$rd root of unity
- Is an integer uniquely determined by its multiplicative order mod every prime
- Estimate $\sum_{k=1}^{n} k^{k-1} \binom{n}{k} (n-k)^{n+1-k}$
- Let $W$ be a subspace of a vector space $V$ . Show that the following are equivalent.
- Closed form for $\prod\limits_{l=1}^\infty \cos\frac{x}{3^l}$
- Number of relations that are both symmetric and reflexive
- On the propagation of singularities in PDE
- What can we say of a group all of whose proper subgroups are abelian?
- How to solve vector-valued first order linear pde?
- Average distance between two random points on a square with sides of length $1$