C1: Distributed Coloring (2): Rubin's Block Lemma

March 04, 2025

• Basics
• Rubin’s Block Lemma
• Reference

This post introduces Rubins’ block lemma.

Basics

$\textbf{Theorem}$. A graph $G$ with order at least three is a block (2-connected) if and only if any two vertices $u,v$ are connected by two internally-disjoint paths.

Rubin’s Block Lemma

$\textbf{Lemma 1}$. If $G$ is a block that is not a clique or an odd cycle, then $G$ contains an induced even cycle with at most one chord.

$\textbf{Proof}$. Let $S$ be a minimal cut set with size $\lvert S \rvert \geq 2$. For any two vertices in a block, there are two internally disjoint paths. We choose two vertices $u,v\in S$. Then, we can can find two shortest paths $P_1$ and $P_2$ (endpoints are $u, v$) in $G\setminus S$ to build a cycle $C$. The only possible chord is $\{u,v\}$. If $C$ is an even cycle, it done. Now, we consider $C$ is odd. Then there exists a path $P$ joining $u, v$ has odd length. If $\{u,v\}$ is there, $P+ uv$ will be chordless even cycle (done). If $\{u,v\}$ is absent, since $G$ is not an odd cycle and $C$ is an odd cycle, then there must be a node $w\in V(G\setminus C)$ where $C$ is chordless.

Now, we divide cases into two.

Case 1: $w$ has at most one neighbor in $C$. Let $x,y \in C$. Let $P_a$ be the path from $x$ to $y$ clockwise and $P_b$ be the path from $x$ to $y$ counterclockwise. Due to the fact that $C$ is an odd cycle, the parity of $P_a$ and $P_b$ is different. We claim that there a path connect $x,y$ from $w$. By Theorem 1, there are two internally-disjoint paths from $w$ to $x$ ( $y$). Then, it is easy to see that there is path from $w$ connecting $x,y$. No matter the parity of such a path, by adding $P_a$ (or $P_b$), we can obtain a chordless even cycle.

Case 2: $w$ has more than one neighbors in $C$. Let $v_1, \ldots, v_k$ be these neighbors. The trick is that $k\geq 3$. We can always create an even cycle with at most one chord by union of $w$ and some $V(P_i)$ where $P_i$ is the path split by $v_1, \ldots, v_k$.

Then, we complete the proof.

Reference

1. Cranston, D.W. and Rabern, L., 2015. Brooks’ theorem and beyond. Journal of Graph Theory, 80(3), pp.199-225.

Vancouver