Lagmental Vicfred

The Principle of Double Counting Proves an Average Identity by Vicfred

Counting incidences first by vertices and then by edges gives the handshaking lemma. The formulas are more useful when each symbol has a job rather than merely decorating the theorem.

Statement

Enumerative combinatorics turns a finite set \(\Omega\) into several reversible descriptions. Binomial coefficients \(\binom nk\) appear whenever a choice forgets order but remembers size.

$$ I=\{(v,e):v\text{ is incident to }e\} $$

The first display fixes the mathematical data. I label it \(\mathsf{data}\) mentally, while the next is the \(\mathsf{claim}\); the bridge between them is the displayed \(\Longrightarrow\), not an automatic implication.

$$ \sum_{v\in V}\deg(v)=2|E| $$

Worked algebra

Now evaluate one representative case. The result should agree with the structural law above, but it is obtained without assuming the conclusion.

$$ |I|=\sum_{v\in V}\#\{e:v\in e\}=\sum_{e\in E}\#\{v:v\in e\}=\sum_{e\in E}2 $$

Conceptual compression

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad I=\{(v,e):v\text{ is incident to }e\},\\[5pt] \mathsf{C}\;&:\quad \sum_{v\in V}\deg(v)=2|E|. \end{aligned} $$

Caveat

A formula with the correct magnitude can still count the wrong objects. The proof must explain whether order, repetition, labels, and empty parts are allowed.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \sum_{v\in V}\deg(v)=2|E| \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Tue 06 March 2018. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.