Graph Theory: (Open) Ear Decomposition Has Number of Ears Equal to Circuit Rank / Nullity / Cyclomatic Number * 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.

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$.