Deelverzamelingen

Beschouw de graaf met de $A_i$'s als toppen. Twee toppen $A_i$ en $A_j$ zijn verbonden als en slechts als hun symmetrisch verschil $\left\{x\right\}$ is voor een zekere $x \in \left\{1,\ldots,n\right\}$, en in dat geval is de boog in kleur $x$. Het gevraagde is gelijkwaardig met de bewering dat een bepaalde kleur niet voorkomt.

Neem een willekeurige cykel in deze graaf. Elke kleur die erin voorkomt, moet er noodzakelijk twee keer in voorkomen. We kunnen dus een van deze bogen in de cykel verwijderen zonder het aantal kleuren te verminderen, terwijl we het aantal cykels in de graaf wel verlagen. Door deze stap te herhalen blijft een acyclische graaf over, met evenveel kleuren als de oorspronkelijke graaf.

We bewijzen dat een acyclische graaf met $n$ toppen ten hoogste $n-1$ bogen heeft. Veronderstel dat er een acyclische graaf bestaat met minstens zoveel bogen als toppen. Door toppen van graad $1$ te verwijderen gaat zowel het aantal toppen als bogen met $1$ naar beneden. Indien we toppen van graad $0$ hebben laten we die gewoon weg. Het resultaat is een acyclische graaf waarin het aantal toppen het aantal bogen nog steeds niet overschrijdt en waar alle toppen van graad tenminste $2$ zijn. Start nu in een willekeurige top en wandel langs de bogen, waarbij langs elke boog maar $1$ keer gewandeld mag worden. Wanneer de wandeling voor het eerst in een top langskomt, kan er altijd een boog gevonden worden om weer weg te gaan, daar de graad van de top tenminte $2$ is. Dus op een zeker ogenblik komt de wandeling in een top waar ze al eerder kwam, wat impliceert dat er toch een cykel in de wandeling zat. Contradictie.