Grafentheorie: bewijs lengte cyclus

[Has]

Hoe bewijs ik dat elke cyclus in G een minimumlengte heeft gelijk aan 5?

G =

[arie]

Een mogelijkheid:

Verdeel de graaf in een rood en een zwart gedeelte, met daartussen blauwe verbindingen:



De rode punten vormen een cykel met lengte 5,
de zwarte punten vormen eveneens een cykel met lengte 5.

Indien een kleinere cykel bestaat, moet die dus zowel rode als zwarte punten bevatten.
Voor elk zwart punt: welk minimum aantal extra rode of zwarte punten moet een cykel vanuit dat punt bevatten?

[Has]

Een mogelijkheid:

Verdeel de graaf in een rood en een zwart gedeelte, met daartussen blauwe verbindingen:



De rode punten vormen een cykel met lengte 5,
de zwarte punten vormen eveneens een cykel met lengte 5.

Indien een kleinere cykel bestaat, moet die dus zowel rode als zwarte punten bevatten.
Voor elk zwart punt: welk minimum aantal extra rode of zwarte punten moet een cykel vanuit dat punt bevatten?

Dat zou dan neerkomen op een cykel van opnieuw een minimumlengte van 5. Bijvoorbeeld 3 extra rode en 1 extra zwarte top.

[arie]

Klopt, en daarmee is het bewijs geleverd.

Wat formeler bewijs je dit met een BFS (https://nl.wikipedia.org/wiki/Breadth-first_search) vanuit elk zwart punt.

Voorbeeld vanuit het meest linker zwarte punt:



De punten op afstand 1 zijn gemarkeerd,
- deze punten zijn onderling niet verbonden (dus geen cykel met lengte 3)
- er is geen enkel ander punt dat 2 van deze punten verbindt (dus ook geen cykel met lengte 4).

Wegens symmetrie van de graaf hoef je hier maar 3 van de 5 zwarte punten te onderzoeken.