Hoi @laurasmulders
De soort graaf zal niet heel veel uitmaken verwacht ik, na wat basis onderzoek naar het probleem zal de graaf "undirected" (ongericht) zijn en "cycles" (cyclussen) bevatten. Maar voor de rest weet ik niet zeker of je die eigenschappen nodig hebt bij het bewijs van de stelling. Op de wikipedia pagina ziet het bewijs er namelijk niet al te lastig uit.
Maarja, ik hoop dat dit je verder helpt.
Jip