Proof of `Taking induced subgraphs and left 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 left factor to be a complete graph on the vertices of : every coefficient is then positive, since a quotient of has at most as many vertices as . The formula therefore exhibits a linear combination of the counts from the disjoint unions of the classes that determines, and the lemma on determined linear combinations places each such disjoint union in . Applying this to the partition whose classes are those of together with a singleton for each vertex outside gives with isolated vertices attached; strips them off. Backwards, (1) ⇒ (2) applied to .