Page 8 - Mathelo Grafentheorie hoofdstuk 1

Grafentheorie

Eigenschap 2
Tel in onderstaande grafen het aantal knopen met een oneven graad.

Graaf 3 Graaf 4
Aantal knopen van een oneven graaf in graaf 3 is gelijk aan 4.
Aantal knopen van een oneven graaf in graaf 4 is gelijk aan 2.

Interactieve GeoGebra versie via deze link https://www.geogebra.org/m/d72ud6s2

Besluit:
Het aantal knopen van een oneven graad in een graaf is even.

Bewijs (in woorden):

De som van alle graden van de knopen is even (eigenschap 1).
Dus is ook de som van de oneven graden en de even graden ook even.
De som van de oneven graden moet dus ook even zijn.

Dit betekent dat het aantal knopen van oneven graden even moet zijn.

Bewijs in formulevorm:

t
Noteer de graad van knoop A als deg(A). Veronderstel dat er k bogen zijn. e
Noem A1, A2, A3, … Ap de knopen met oneven graad. n
Noem B1, B2, B3, … Bq de knopen met even graad. . o
l
e
Er geldt: deg(A1) + deg(A2) + deg(A3) + … +deg(Ap) + deg(B1) + deg(B2) + deg(B3) + … + deg(Bq) = 2k h
t
a
m
Dus is: deg(A1) + deg(A2) + deg(A3) + … +deg(Ap) = 2k – (deg(B1) + deg(B2) + deg(B3) + … + deg(Bq))
.
w
w
Het linkerlid is even omdat het verschil van twee even getallen in het rechterlid ook even is.
w

© 2021 Ivan De Winne ivan@mathelo.net 7