Een boom is een verbonden grafiek zonder cycli. Een bipartiete grafiek is een grafiek waarvan de hoekpunten kunnen worden verdeeld in twee onsamenhangende sets, zodat elke rand een hoekpunt in de ene set verbindt met een hoekpunt in de andere set.

Om aan te tonen dat elke boom een ​​bipartiete grafiek is, kunnen we inductie gebruiken op het aantal hoekpunten in de boom.

Basisscenario:een boom met één hoekpunt is triviaal tweeledig.

Inductieve stap:Neem aan dat elke boom met n hoekpunten tweeledig is. Laat T een boom zijn met n+1 hoekpunten. We kunnen een bipartiete grafiek construeren uit T door één hoekpunt als een deel van de bipartitie te nemen en de overige n hoekpunten als het andere deel. De randen van de bipartiete grafiek zijn hetzelfde als de randen van T.

Door inductie is elke boom een ​​bipartiete grafiek.