regel van Euler

© h.hofstede (h.hofstede@hogeland.nl)

De regel van Euler.

Ik herhaal eerst even het hulpstellinkje van de vorige les:

De som van de graden van alle facetten van een planaire graaf
is gelijk aan het dubbele van aantal verbindingslijnen van die graaf.

Euler (nee toch? alwéér hij?) heeft een geweldige formule ontwikkeld voor het verband tussen het aantal knooppunten, verbindingslijnen en facetten van een samenhangende planaire graaf. Die formule ziet er zó uit:

f + K = V + 2

Daarin is f het aantal facetten, K het aantal knooppunten, en V het aantal verbindingslijnen.

Het bewijs met volledige inductie
We nemen volledige inductie naar het aantal facetten.

beginstap
Als f = 1 is elke verbindingslijn een kritieke verbinding (zo'n graaf heet een boom zullen we later zien).
In dat geval is V = K - 1.
Dat is heel eenvoudig te zien: ga hem maar tekenen!
• Begin met een knooppunt en kies een willekeurige verbindingslijn. Die loopt naar een nieuw knooppunt toe.
• Kies één van de al getekende knooppunten en een nieuwe verbindingslijn (die is er altijd want de graaf is samenhangend)
• Die loopt weer naar een nieuw knooppunt.
Ga zo door totdat de graaf getekend is.

Elke verbindingslijn heeft een nieuw knooppunt opgeleverd, dus het aantal knooppunten is één groter dan het aantal verbindingslijnen. Waaróm leverde elke lijn eigenlijk een nieuw knooppunt?
Nou, als dat niet zo was hebben we een lus gemaakt en is er niet meer één facet, maar een binnen- en een buitengebied van die lus!! Dat kan dus niet.

de inductiestap
Stel dat de stelling klopt voor alle grafen tot en met n - 1 facetten.
Neem nu een graaf met n facetten.
Kies van deze graaf een verbindingslijn v die geen lijnsnede is (als dat niet kan is G weer een boom en geldt het bewijs van de beginstap hierboven).
Laat deze verbindingslijn weg, dan heb je graaf G - v
Nu geldt:
V(G - v) = V(G) - 1 (je liet immers één v weg)
K(G - v)= K(G)     (je liet geen knooppunt weg)
f(G - v) = f(G) - 1   (omdat v geen lijnsnede was)

Omdat de regel geldig is voor G - v (inductie-aanname)   geldt
f(G - v) + K(G - v) = V(G - v) + 2
invullen:
f(G) - 1 + K(G) = V(G) - 1 + 2
⇒ f(G) + K(G) = V(G) + 2
Daarmee is de stelling bewezen!

■

of: Q.E.D., dat staat erudieter.
of: Kloar! zoals wij in Groningen zeggen....

Het bewijs met boerenverstand.

Ga de graaf gewoon tekenen!
Stel dat je de graaf hebt waarvoor de regel geldt, dan kun je die graaf als volgt uitbreiden:

•

Teken er een nieuwe verbindingslijn bij. Dan wordt f één groter en V ook, en blijft de regel geldig.

•

Teken er een nieuw knooppunt bij. Daar moet een verbindingslijn aan vast, dus wordt V één groter en K ook, en blijft de regel geldig.

Het allereerste begin is een graaf met één enkel knooppunt, en daarvoor geldt 1 + 1 = 0 + 2 dus dat klopt.
Dus het blijft kloppen.
Kloar!

Twee snelle gevolgen van deze regel (nog steeds voor enkelvoudige planaire grafen).

als K ≥ 3 dan is V ≤ 3K - 6

Laten we de stelling bewijzen voor een volledig verbonden graaf, dan geldt hij ook voor alle anderen (die hebben immers alleen maar minder verbindingslijnen)
Het hulpstellinkje helemaal bovenaan deze les:   (som van graden van de facetten) = 2 • V
Maar elk facet heeft graad minstens 3 want de graaf was volledig verbonden dus de som van de graden is minstens 3f
Dat betekent dus dat 2V ≥ 3f dus   ²/₃V ≥ f
Invullen in de Eulervergelijking:    ²/₃V + K ≥ V + 2   ⇒ 3K - 6 ≥ V

■

δ ≤ 5 (δ is de laagst voorkomende graad van alle knooppunten)

δ • K ≤ som van alle graden van de knooppunten = 2V ≤ 6K - 12 (volgens de vorige stelling)
12 ≤ K • ( 6 - δ)
6 - δ mag niet nul of lager worden, dus moet gelden δ ≤ 5
(de gevallen K = 1 en K = 2 zijn triviaal)

■

Het regeltje: 12 ≤ K • ( 6 - δ) in het bewijs bij 2 geeft meteen een aantal conclusies over volledige grafen:

•

Voor K₅ is K = 5 en δ = 4 en staat er 12 ≤ 5 • (6 - 4) = 10. Onzin, dus K₅ is niet-planair.

•

Voor K₆ is K = 6 en δ = 5 en staat er 12 ≤ 6 • (6 - 5) = 6. Onzin, dus K₆ is niet-planair

•

De grafen K₇ en hoger hebben δ = 6 en hoger en zijn dus allemaal niet-planair.

Een interessante graaf: K_{3, 3}

In opgave 1 van de vorige les heb je (misschien) het volgende probleem door slim te redeneren opgelost:

Deze drie huisjes moeten met verbindingslijnen in dit vlak elk met gas, water en licht worden verbonden.
De graaf die dat doet zie je ernaast, en hij heet K_{3, 3}. (Later zullen we het gaan hebben over bipartiete grafen, daar is dit er eentje van).
Als die leidingen elkaar niet mogen snijden gaat het er dus om of deze graaf planair is of niet.....Nou, dat is niet zo!

Het bewijs.
Omdat K_3,3 uit twee groepen knooppunten bestaat die onderling niet zijn verbonden (de "huisjesgroep" en de "voorzieningengroep") zal een cykel van K_3,3 dus uit minstens 4 verbindingslijnen moeten bestaan (huisje - voorziening - ander huisje - andere voorziening - eerste huisje)
Dat betekent dat elk facet van K_{3, 3} graad minstens 4 heeft.
Maar de som van de graden van die facetten is gelijk aan 2V (alweer het hulpstellinkje helemaal aan het begin)

4f ≤ som van graden van f = 2V = 18 dus f ≤ 4 ('t is een geheel getal)

de Eulervergelijking geeft : f + K = V + 2 geeft f + 6 = 9 + 2 dus f = 5

Die twee zijn tegenstrijdig dus is K_{3, 3} geen planaire graaf.

Gevolgen voor ruimtelijke lichamen!

Omdat we in de vorige les al zagen dat planaire grafen in het platte vlak en op een bol met elkaar overeenkomen (via de stereografische projectie) zegt de regel van Euler ineens iets over eigenschappen van een ruimtelijk lichaam!
Immers, de vlakken van zo'n lichaam komen overeen met de facetten van de graaf, de verbindingslijnen worden de ribben en de knooppunten worden de hoekpunten!!!

Een fantastisch resultaat:

Vlakken + Hoekpunten = Ribben + 2

(Oké, laat ik eerlijk zijn, ik liet me even meeslepen. De hoekpunten moeten dan wel op de bol liggen..... of op één of ander misvormd soort "bol" waarvoor die projectie werkt. Er mogen daarom in ieder geval geen "deuken" in zitten, dus die lichamen moeten voorlopig wel convex zijn. Toch vind ik het nog steeds fantastisch. Als er een Euler-fanclub zou zijn, dan zou ik er graag voorzitter van worden).

Laten we het even checken voor de vijf Platonische lichamen (we weten natuurlijk al dat het klopt, maar het geeft elke keer weer een kick, nietwaar?)

Het wordt helemaal te gek als je je realiseert dat die tweede en derde elkaars duale graaf zijn, en die vierde en vijfde ook, en dat die eerste zijn eigen duale graaf is! Als je de middens van de ribben (of vlakken) van een lichaam met elkaar verbindt krijg je de duale partner!

OPGAVEN

1.	Als de facetten van G bestaan uit alleen maar driehoeken, dan geldt V = 3K - 6 Toon dat aan.

2.	Waarom kun je de knooppunten van een planaire graaf altijd met 6 kleuren kleuren?

3.	Als de graad van elk knooppunt van een graaf minstens g is, dan geldt V ≥ ¹/₂ • g • K Toon dat aan.

4.	In een planaire graaf zonder driehoeken geldt f ≤ ¹/₂ • V Toon dat aan.