Waarom zijn er twaalf 2-reguliere grafen met vijf punten?

Stap 1.

De graaf G moet samenhangend zijn.

Bewijs: Stel G is niet samenhangend . Dan is er minstens één stuk van de graaf dat uit 2 punten of minder bestaat dat niet samenhangt met de andere 3 punten, en deze 1 of 2 punten kunnen maximaal graad 1 van verbondenheid hebben (immers, alleen maar met elkaar). Dit is in tegenspraak met de definitie van 2-regulariteit.

Stap 2.

De hele graaf G bestaat uit een enkele cykel.

Bewijs:

De graaf G kan geen boom zijn. Deze hebben immers als eigenschap dat als een enkele lijn verwijderd zou worden (en we zo een nieuwe graaf G’ krijgen) , deze nieuwe graaf G’ niet meer samenhangend is. Dus zouden er dan punten met graad 1 in onze oorspronkelijke graaf G zijn , hetgeen in strijd is met de 2-regulariteit van G.

Als G dus geen boom is moet G een cykel bevatten. Immers, als na het verwijderen van een lijn e de resultaatgraaf G' nog steeds samenhangend is, is lijn e onderdeel van een cykel in de oorspronkelijke graaf G.

Zo'n cykel kan uit 3, 4, of 5 punten bestaan. Maar aangezien alle punten van de graaf graad 2 hebben, en alle punten in een cykel al minimaal graad 2 hebben, kan er geen punt buiten de cykel liggen. Zou dat wel het immers geval zijn, dan zou in verband met de samenhangendheid van G er minstens één punt (op de cykel, en ook nog verbonden met minstens een punt buiten de cykel) met graad 3 of meer zijn. En dat is wederom in strijd met de definitie van 2-regulariteit. Dus behoren alle 5 punten tot de cykel, en is de hele graaf een cykel.

Stap 3.

Dus reduceert de vraag tot: op hoeveel manieren kunnen we een ongelabelde cykel C5 labelen ?

Punt 1 is vrij te kiezen omdat voor een graaf enkel de onderlinge verbindingen er toe doen (twee grafen die enkel verschillen omdat ze geroteerd zijn, maar verder dezelfde onderlinge verbindingen hebben worden als dezelfde beschouwd). Voor punt 2 kunnen we dan 4 posities kiezen , voor punt 3 nog 3, voor punt 4 nog 2, en punt 5 heeft dan de laatst overgebleven positie.

Kortom: 4! = 24 manieren.

Maar aangezien dit steeds paren van gespiegelde grafen zijn (immers het pad 123451 is hetzelfde als het pad 154321, alleen omgekeerd doorlopen), en gespiegelde grafen ook als hetzelfde beschouwd worden (immers, de onderlinge verbindingen liggen dan nog steeds hetzelfde) komen we op 12 uit.