Graph Theory: (Open) Ear Decomposition Has Number of Ears Equal to Circuit Rank / Nullity / Cyclomatic Number

Question

• The Wikipedia article on 'Circuit rank' tells me that 'In any biconnected graph with circuit rank $r$, every open ear decomposition has exactly $r$ ears.'
• It refers to Whitney's 1932 paper 'Non-separable and planar graphs' - especially Theorem 18 - to make that connection.
• Theorem 18. If $G$ is a non-separable graph of nullity $N>1$, we can remove an arc [edge] or suspended chain [internally disjoint path] from $G$, leaving a non-separable graph $G'$ of nullity $N-1$.
• Unfortunately, I cannot deduce from the theorem the connection between circuit rank and number of ears in an ear decomposition.

Answer 1

Both the circuit rank and the number of ears in an ear decomposition can be computed from the number of vertices and edges in the graph.

Suppose the graph $G$ is $2$-connected, and has $n$ vertices and $m$ edges.

1. The maximum number of edges in an acyclic graph on $n$ vertices is $n-1$, and we can reach that by deleting all edges outside a spanning tree of $G$. If we do that, we are deleting $m-(n-1) = m-n+1$ edges, so the circuit rank is $m-n+1$.
2. Suppose that $G$ has an ear decomposition that begins with a cycle and adds $k-1$ more ears. In the cycle, the number of vertices equals the number of edges. Adding an ear of length $\ell$ adds $\ell$ edges and $\ell-1$ vertices, increasing the difference $|E|-|V|$ by $1$. Therefore after adding $k-1$ ears, the difference is $k-1$; but we know the difference is $m-n$. So $k-1 = m-n$, or $k = m-n+1$.