Er hvert træ en todelt graf?

Et træ er en sammenhængende graf uden cyklusser. En todelt graf er en graf, hvis toppunkter kan opdeles i to usammenhængende sæt, således at hver kant forbinder et toppunkt i det ene sæt med et toppunkt i det andet sæt.

For at vise, at hvert træ er en todelt graf, kan vi bruge induktion på antallet af hjørner i træet.

Grundtilfælde:Et træ med et toppunkt er trivielt todelt.

Induktivt trin:Antag, at hvert træ med n toppunkter er todelt. Lad T være et træ med n+1 hjørner. Vi kan konstruere en todelt graf ud fra T ved at tage det ene toppunkt som den ene del af topartitionen og de resterende n toppunkter som den anden del. Kanterne på den todelte graf er de samme som kanterne på T.

Ved induktion er hvert træ en todelt graf.