Double Counting Vertex-Edge Incidences

Counting the Same Objects in Two Ways

A useful graph proof often begins by choosing a collection of objects that can be counted from two different viewpoints. For degree arguments, the objects are vertex-edge incidences: an incidence is a pair \((v,e)\) in which \(v\) is an endpoint of \(e\). Counting incidences by vertices brings in degrees; counting them by edges brings in the fact that each edge has two endpoints. The resulting identities are simple, but they give exact constraints on how degrees, edges inside a set, and edges crossing its boundary fit together.

Throughout, graphs are finite and simple. Write \(G=(V,E)\), with \(n=|V|\) and \(m=|E|\). The degree \(\deg(v)\) is the number of edges incident with vertex \(v\). For a vertex set \(S\subseteq V\), \(G[S]\) is the induced subgraph on \(S\): it contains precisely the edges of \(G\) whose two endpoints both lie in \(S\). Write \(\partial(S)\) for the set of edges with exactly one endpoint in \(S\). These are the edges crossing between \(S\) and \(V\setminus S\).

Since the graph is simple, each edge has two distinct endpoints. Thus every edge contributes exactly two incidences to \(I(G)\). On the other hand, a vertex \(v\) belongs to exactly \(\deg(v)\) incidences. This is the basic double count: enumerate the same incidence set once by its vertices and once by its edges.

The Degree-Sum Identity

Proof. Consider \(I(G)\). For each vertex \(v\), there are \(\deg(v)\) incidences with first coordinate \(v\), so counting by vertices gives \(|I(G)|=\sum_{v\in V}\deg(v)\). Each edge has exactly two endpoints, so counting by edges gives \(|I(G)|=2|E|\). Equating these two counts proves the identity. If \(V=\varnothing\), then \(E=\varnothing\), both sides are \(0\), and the same identity holds. \(\square\)

This argument establishes the identity from the definitions; it does not assume a named result. It is important that each edge contributes two incidences, while a vertex contributes as many incidences as its degree. In particular, a degree sum counts edges with both endpoints in the set being summed twice, not once.

A useful special case follows directly. If every vertex has the same degree \(r\), then the degree sum is \(rn\), because it has \(n\) terms each equal to \(r\). Hence \(rn=2m\). This is an exact constraint on a regular graph: its order, common degree, and size cannot be chosen independently. The argument also includes the graph with no vertices, where both sides are zero.

Counting Incidences at a Vertex Subset

Now count only incidences whose vertex lies in a chosen subset \(S\). The vertex-based count is \(\sum_{v\in S}\deg(v)\). To count by edges, separate edges into three types: those with both endpoints in \(S\), those with exactly one endpoint in \(S\), and those with no endpoint in \(S\). The last type contributes no incidence to \(I(S)\). Each edge of \(G[S]\) contributes two, and each edge of \(\partial(S)\) contributes one.

Proof. Count \(I(S)\) by its vertex coordinate. A vertex \(v\in S\) contributes one incidence for each edge incident with it, giving \(|I(S)|=\sum_{v\in S}\deg(v)\). For the edge-based count, an edge with both endpoints in \(S\) contributes two incidences; these are exactly the edges of \(G[S]\). An edge with exactly one endpoint in \(S\) contributes one; these are exactly the edges of \(\partial(S)\). An edge with no endpoint in \(S\) contributes zero. Therefore \(|I(S)|=2|E(G[S])|+|\partial(S)|\), which proves the identity. If \(S=\varnothing\), all three quantities are zero, so the formula remains valid. \(\square\)

The formula identifies the two different ways a degree sum over \(S\) receives contributions. Edges internal to \(S\) are counted at both their endpoints; edges crossing out of \(S\) are counted only at their endpoint in \(S\). Rearranging gives an exact way to recover the boundary size: \[ |\partial(S)|=\sum_{v\in S}\deg(v)-2|E(G[S])|. \] The right side must therefore be a nonnegative integer. It is not an estimate: once the degrees in \(S\) and its internal edges are known, the number of crossing edges is determined.

The same reasoning applies when a set and its complement are considered together. Each crossing edge contributes one incidence on the \(S\) side and one on the \(V\setminus S\) side. Thus the crossing edges appear in both subset degree sums, while an edge internal to either side appears twice in that side's sum and not at all in the other. This lets us check the two sides separately rather than treating the whole graph as an undivided set.

Using the Identities Carefully

These counts are useful in proofs because they turn local information about degrees into exact information about edges. For example, if the degrees of the vertices in \(S\) and the edges inside \(S\) are specified, then the subset identity fixes the number of edges leaving \(S\). Conversely, if the internal edges and crossing edges are known, the identity fixes the degree sum on \(S\). In a proof, this can expose incompatible requirements: a proposed configuration cannot exist if its stated quantities do not satisfy the equation.

The boundary formula also gives immediate consistency checks. Since \(|\partial(S)|\geq0\), every \(S\subseteq V\) must satisfy \[ \sum_{v\in S}\deg(v)\geq 2|E(G[S])|. \] This inequality is simply the exact identity with the nonnegative boundary term retained. Equality holds precisely when \(\partial(S)=\varnothing\), which means no edge has exactly one endpoint in \(S\). Indeed, the identity says the difference between its two sides is \(|\partial(S)|\), and a set has no crossing edges exactly when that number is zero.

Several limiting cases help check that the formula is being applied with the right edge counts. For \(S=V\), there are no crossing edges, so the subset identity becomes the full degree-sum identity. For a single vertex \(S=\{v\}\) in a simple graph, \(G[S]\) has no edges, and every edge incident with \(v\) crosses the boundary; the formula becomes \(\deg(v)=|\partial(\{v\})|\). For an isolated vertex, both sides of this last equality are zero. For \(S=\varnothing\), there are no vertices, internal edges, or crossing edges.

Common mistake: counting an internal edge only once. In the first graph example, for \(S=\{a,b,c\}\) there are three internal edges and one crossing edge. A wrong calculation would say that the degree sum is \(3+1=4\), counting each internal edge once. But the actual degree sum is \(2+2+3=7\). Each internal edge has two endpoints in \(S\), so it contributes two incidences; the corrected count is \(2\cdot3+1=7\). A related error is to count a crossing edge twice in the sum over \(S\). It has only one endpoint in \(S\), so it contributes one incidence there; its other incidence belongs to the sum over \(V\setminus S\).

Before using double counting in a proof, identify the objects first and specify exactly which of them are being counted. Here the objects are pairs \((v,e)\), not edges alone. Then classify their contributions: for the full graph, every edge contributes two; for a subset, internal edges contribute two, boundary edges one, and edges outside contribute zero. That classification is what makes the equations reliable.