Ett träd är en sammankopplad graf utan cykler. En tvådelad graf är en graf vars hörn kan delas upp i två disjunkta uppsättningar så att varje kant förbinder en vertex i en uppsättning med en vertex i den andra uppsättningen.
För att visa att varje träd är en tvådelad graf kan vi använda induktion på antalet hörn i trädet.
Basfall:Ett träd med en vertex är trivialt tvådelat.
Induktivt steg:Antag att varje träd med n hörn är tvådelat. Låt T vara ett träd med n+1 hörn. Vi kan konstruera en tvådelad graf från T genom att ta en vertex som en del av bipartitionen och de återstående n hörnen som den andra delen. Kanterna på den tvådelade grafen är desamma som kanterna på T.
Genom induktion är varje träd en tvådelad graf.
