Double Counting Pairs and Common Neighbors

Counting the Same Structure in Two Ways

Many graph arguments become clearer when we count a collection of objects in two different ways. For instance, one can count pairs of vertices that have a common neighbor by first choosing the neighbor, or by first choosing the pair. The two counts must agree. This simple principle yields useful equalities, checks computations, and can force restrictions on a graph.

Throughout, graphs are finite and simple: there are no loops or multiple edges. The neighborhood \(N(v)\) of a vertex \(v\) is the set of vertices adjacent to it, and \(\deg(v)=|N(v)|\). For distinct vertices \(u,v\), define their common-neighbor count by

We count unordered pairs \(\{u,v\}\), so each pair is considered once, not once in each order. A common neighbor \(x\) of \(u\) and \(v\) gives a length-two path \(u,x,v\), with endpoints \(u,v\). The endpoints are distinct, and in a simple graph \(x\) differs from both of them.

The Basic Common-Neighbor Identity

Proof. Count the objects \((x,\{u,v\})\) for which \(u\) and \(v\) are distinct neighbors of \(x\). If \(x\) is fixed, there are \(\deg(x)\) choices of its neighbors and therefore \(\binom{\deg(x)}{2}\) unordered pairs of distinct neighbors. Summing over \(x\in V\) gives the left-hand side. Alternatively, fix the unordered pair \(\{u,v\}\). The possible choices of \(x\) are exactly the common neighbors of \(u\) and \(v\), so there are \(c(u,v)\) choices. Summing over all unordered pairs gives the right-hand side. Both counts enumerate the same objects. If \(|V|<2\), there are no eligible pairs, and every degree is at most one, so both sides are zero. \(\square\)

The identity counts length-two paths by their middle vertex on the left and by their pair of endpoints on the right. The endpoints need not be adjacent. This matters: the right-hand sum includes all unordered pairs, whether or not they form an edge.

Counting Across a Partition

Sometimes only pairs separated by a chosen partition are relevant. Let \(A\) and \(B\) be disjoint sets whose union is \(V\); either set may be empty. For each vertex \(x\), the sets \(N(x)\cap A\) and \(N(x)\cap B\) record its neighbors in the two parts.

Proof. Count triples \((x,a,b)\) such that \(a\in A\), \(b\in B\), and \(xa,xb\in E\). For fixed \(x\), there are \(|N(x)\cap A|\) choices for \(a\), independently of the \(|N(x)\cap B|\) choices for \(b\). This gives the product on the left, and summing over \(x\) counts all such triples. Alternatively, fix \(a\in A\) and \(b\in B\). The eligible vertices \(x\) are exactly the common neighbors of \(a\) and \(b\), giving \(c(a,b)\) choices. Summing over the cross-part pairs gives the right-hand side. If either part is empty, both sides are zero: each product has a zero factor and there are no cross-part pairs. \(\square\)

This identity counts length-two paths whose endpoints lie in different parts. The middle vertex can lie in either part. In particular, the endpoints of these paths are always distinct because the parts are disjoint.

Using the Identity to Obtain Constraints

A useful special case occurs when the graph is triangle-free, meaning it has no three vertices that are pairwise adjacent. If \(u\) and \(v\) are adjacent, they cannot have a common neighbor: such a vertex together with the edge \(uv\) would form a triangle. Thus all contributions on the common-neighbor side come from nonedges.

Proof. Apply the basic identity and split its right-hand sum into adjacent and nonadjacent pairs. For an adjacent pair \(u,v\), a common neighbor would make a triangle, so \(c(u,v)=0\). The sum over adjacent pairs is therefore zero, leaving exactly the sum over nonedges. If every nonadjacent pair has at most one common neighbor, each term in that remaining sum is at most one. There are \(\binom{n}{2}-|E|\) nonedges, since a simple graph has \(\binom{n}{2}\) unordered vertex pairs in total and \(|E|\) of them are edges. This proves the inequality. \(\square\)

Four-Cycles from Common Neighbors

Common-neighbor counts can also count cycles. In the formula below, a four-cycle is counted as a cycle subgraph: changing its starting vertex or reversing its direction does not create a new cycle.

Proof. First fix an unordered pair \(\{u,v\}\) and choose two distinct common neighbors \(x,y\). The edges \(ux,xv,vy,yu\) form the four-cycle \(u,x,v,y,u\). Its four vertices are distinct: \(u\ne v\), \(x\ne y\), and neither common neighbor can equal \(u\) or \(v\), since there are no loops. Conversely, a four-cycle has two pairs of opposite vertices. For either opposite pair, its two other vertices are distinct common neighbors. Thus each four-cycle gives exactly two choices counted by the sum, one for each opposite pair, and every choice in the sum gives a four-cycle. The sum counts each four-cycle twice, so division by \(2\) gives the number of four-cycles. If there are fewer than four vertices, the sum is zero because no pair has two distinct common neighbors, as required. \(\square\)

A Common Counting Mistake

Do not count only adjacent pairs in the basic identity. The left-hand side counts every pair of neighbors of each vertex, whether or not those two neighbors are adjacent. Therefore the matching sum on the right must include all unordered pairs, not just edges.

For a concrete error, take the graph with \(V=\{1,2,3\}\) and \(E=\{12,23\}\). Its degrees are \(1,2,1\), so the degree-side sum is \(0+1+0=1\). The only common neighbor belongs to the nonedge pair \(\{1,3\}\), for which \(c(1,3)=1\). If one incorrectly sums only over edges, both edge pairs have common-neighbor count zero, producing \(0\), which fails to match the degree-side total. Including all three pairs gives \(c(1,2)+c(1,3)+c(2,3)=0+1+0=1\), restoring the identity.

There is a related distinction when counting triangles: \(\sum_{\{u,v\}\in E}c(u,v)\) counts each triangle three times, once for each of its edges. It is not the basic identity, whose right-hand side sums over all pairs and counts length-two paths by their endpoints.