Un albero è un grafo connesso senza cicli. Un grafo bipartito è un grafo i cui vertici possono essere divisi in due insiemi disgiunti in modo tale che ogni bordo colleghi un vertice in un insieme a un vertice nell'altro insieme.
Per dimostrare che ogni albero è un grafo bipartito, possiamo usare l'induzione sul numero di vertici dell'albero.
Caso base:un albero con un vertice è banalmente bipartito.
Passo induttivo:supponiamo che ogni albero con n vertici sia bipartito. Sia T un albero con n+1 vertici. Possiamo costruire un grafo bipartito da T prendendo un vertice come una parte della bipartizione e i restanti n vertici come l'altra parte. Gli spigoli del grafo bipartito sono gli stessi di T.
Per induzione ogni albero è un grafo bipartito.
