combinatoriek 3

Opgave - IMOSL 2004 vraag 25

De volgende handeling is toegestaan op een eindige graaf: kies een willekeurige cykel van lengte 4 (als er zijn), en kies een willekeurig boog in die cykel, en verwijder die van de graaf. Voor een vast natuurlijk getal $n\geq4$, vind het minimum aantal bogen van een graaf dat verwijderd kan worden door herhaaldelijk deze handeling uit te voeren op de complete graaf met $n$ knopen.