Block Graph

Definition (Block)

In a connected Graph $G$, a block is a maximal subgraph with no Cut vertices. In particular, maximal refers to $\max |V(G)|$

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzcd}\n\ta & b & c\n\t\\arrow[no head, from=1-1, to=1-2]\n\t\\arrow[no head, from=1-2, to=1-3]\n\\end{tikzcd}\n\\end{document}"$

source code

Here, $b$ is the cut vertex and $a,c$ would be blocks.

Lemma (All Edges Exist in a Block)

Every edge $e$ in a connected graph is contained in the some block.

Proof: If we just take a graph of just some edge $e$, it is a connected subgraph without a cut vertex. So it must be part of a maximal subgraph (i.e. a block.)

Lemma (Block Intersection is Singleton or Empty)

Intersection of two blocks is always either empty or a single cut vertex. Formally, if $B_1$ and $B_2$ are some blocks, then

$$|V(B_1)\cap V(B_2)|\in \{0,1\}$$

Proof:

Claim A: If we have two blocks $B_1,B_2$, then if $V(B_1)\cap V(B_2)$ contains $v,w$, then $V(B_1)\cup V(B_2)$ has no cut vertices.

WTS that any vertex we remove leaves $B_1\cup B_2$ connected. WLOG, if $B_2$ had a vertex removed, it would still be connected since it has no cut vertices. WLOG, suppose we removed $w$. Then $B_1-\{w\}$ is connected, and $B_2-\{w\}$ is connected. But then from any vertex in $B_1$, we can reach $v$ and then reach any vertex in $B_2$ and vice versa.

Therefore $(V(B_1)\cup V(B_2))-\{w\}$ is connected. But then this is a contradiction because their union is a larger subgraph with no cut vertices.

Claim B: We cannot have $V(B_1)\cap V(B_2)=\{v\}$ where $v$ is a non-cut vertex.

If this is true, then removing $v$ does not disconnect the graph. Indeed, there is a Path $P:u\to w$ where $u\in V(B_1)$ and $w\in V(B_2)$. Now if we have $B_1\cup B_2\cup P$, then this is connected subgraph with no cut vertex. So where is the cut vertex?

Suppose we cut $v$. Then we can use $P$ to connect $B_1$ and $B_2$. WLOG if we cut some vertex $x\in B_1$, then the subgraph is still trivially connected. Suppose we cut some $x$ in the path $P$. But then without $x$, $B_1,B_2$ are still connected (by vertex $v$).

So this means we can decompose our connected graph into smaller block subgraphs that are connected by one vertex, which are our cut vertices.

Definition (Block Graph)

Let $G$ be a finite connected graph. Then the block graph of $G$ is a new graph with

$$\begin{array}{rl}V& =\{\text{blocks of }G\}\cup \{\text{cut vertices of }G\}\\ E& =\text{edge between }B,v\text{ if }v\in V(B)\end{array}$$

Essentially, we are condensing the blocks into their own “vertex” and keeping the edges of the cut vertices.

Lemma (Block Graphs are Bipartite)

If $G$ is a finite connected graph, then its block graph is a Bipartite Graph. Indeed, we have two types of vertices, we simply have one be colored white and the other be colored black. And by Lemma (Block Intersection is Singleton or Empty), then we cannot have an edge connecting to blocks, as they would just be combined to a single block vertex.

Lemma (Block Graphs are Trees)

A block graph is always a Tree.

Proof: We need to show two properties:

1. Block graphs are always connected.
2. fsd

For $(1)$, let $B_1,B_2$ be two arbitrary blocks. We can assume both vertices are blocks. The proof is the same otherwise. Since the original graph $G$ was connected, then we have some path $P$ in $G$, and follow it for any vertex $u\in B_1$ and $v\in B_2$. If there is an edge $(u,v)$ we are done.

Suppose not. Then we can follow path; we will encounter other partitions and cut vertices.

$$P:B_1\to c_1\to B_3\to c_3\to \cdots \to c_2\to B_2$$

Since $u,v$ and $B_1,B_2$ were arbitrary, then we are done.

Lemma (Block Graphs have No Cycles)

A block graph has no cycles.

Proof: Assume by contradiction there is a cycle in the block graph. Then we have some cycle from $B_1$ to $B_n$.

But if we take the union $B_1\cup B_2\cup \cdots \cup B_n$, then we’d have no cut vertex. Suppose we removed some vertex $x\in B_i$. Each individual $B_j$ without $x$ is still connected. Indeed, we still share

$$B_1\to B_2\to \cdots \to B_i$$

and

$$B_n\to B_{n-1}\to \cdots \to B_i$$

with $B_1\to B_n$. But then as it is still connected, then we have new block, which is the union.