Reminder: This post contains 1804 words
· 6 min read
· by Xianbin
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
- Cranston, D.W. and Rabern, L., 2015. Brooks’ theorem and beyond. Journal of Graph Theory, 80(3), pp.199-225.
Vancouver