Proof of `Lovász's theorem` (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
Lovász's homomorphism matrix lemma. Every homomorphism factors as a strongly surjective homomorphism onto its image followed by an injective one; the image is isomorphic to a unique member of the family, and each homomorphism admits exactly factorisations through . Counting gives with the matrix of strongly surjective counts, the diagonal of automorphism counts and the matrix of injective counts. Ordering the family by number of vertices, then by number of edges, makes lower and upper triangular, both with positive diagonal, so all three factors are invertible and hence so is .