Ear

Definition (Ear)

Let $G\subset H$ be a subgraph. An ear of $H$ is a Path in $G$ whose endpoints are in $H$ but no other points are. Example:

$"\\begin{document}\n\\begin{tikzpicture}\n$

source code

Theorem (Ears Do Not Add Cut Vertices)

If $H$ has no cut vertex, and if $E$ is an ear for $H$, then $E+H$ has no cut vertex.

Proof:

Consider subgraph $H$ and ear $E$ with endpoints $u,v\in V(H)$. I claim that we have no cut vertices in $H+E$. We have three cases:

1. If we removed some $x\in V(H)-\{u,v\}$ that is not an endpoint of ear $E$, then as $H$ has no cut vertex and $E$ is still connected, $E+H-\{x\}$ is still connected.
2. If we removed some $x\in \{u,v\}$, then $E$ is still connected through the other endpoint to $H$, which is connected. Thus the graph is still connected.
3. If we removed some $x\in V(E)-\{u,v\}$, some “internal” point of $E$, then one half of $E$ is still connected by $u$ and the other by $v$, so the graph is still connected.

Since $E+H-\{x\}$ is still connected for any $x$, then $E+H$ has no cut vertices.

Theorem (Ear Decomposition)

A block $B$ is either equal to Complete Graph $K_2$ xor a Cycle with ears.

Proof:

Let $B$ be a block. We know from Lemma (Block-Cycle Characterization) that $B$ is $K_2$ xor a cycle. If $B=K_2$ we are done. Let $B$ contain a Cycle $C$. We want to show that we can iteratively add ears to form $B$.

Let $H_0=C$ be our initial subgraph of $B$. Assume we have some subgraph $H_i$ of $B$ after adding $i$ ears. If $H_i=B$ we are done. Let $H_i\ne B$. Since $B$ is connected, $\exists$ edge $e=(u,v)$ where $u\in V(H_i)$ and $v\notin V(H_i)$.

If all edges of $H_i$ connected to only vertices of $H_i$ then $H_i$ is a disconnected component, which is impossible since $B$ is connected.

Consider $B-\{u\}$. This is a block and so it has no cut vertices, and is connected. This gives some path $P^{\prime }$ in $B-\{u\}$ from $v$ to some other vertex in $H_i-\{u\}$. This gives us path $P$ where

$$E=(u,v,\dots ,w)$$

where $w$ is the first vertex in in $H_i$ formed by the path $P$, which gives us ear $E$. The internal vertices of $E$ are not in $H_i$.

We can repeat this, so that $H_{i+1}=H_i+E$. Since $B$ is finite, we can repeat this until we have some $k$ where $H_k=B$.

Example 1

See Definition (Ear) to see a graph. Although in class we called it a Theta Graph, here you can just imagine we moved $x_1,x_2$ inside the $v_i$ square, rotate it slightly and we have some “theta-looking” graph.

Here the graph has $2$ vertices with $3$ disjoint paths between them. This is an example of starting with a cycle and adding an ear.