Proof of `Contracting edges and right lexicographic products` (1st statement)
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
, (2) ⇔ (3). Forwards, take the right factor to be a complete graph on the vertices of : every coefficient is then positive, since the disjoint union of the classes is a graph on and maps into that complete graph. The formula therefore exhibits a linear combination of the counts from the quotients that determines, and the lemma on determined linear combinations places each quotient in ; every contraction is such a quotient. Backwards, (1) ⇒ (2) applied to .