Un arbre est un graphe connecté sans cycles. Un graphe biparti est un graphe dont les sommets peuvent être divisés en deux ensembles disjoints de telle sorte que chaque arête relie un sommet d'un ensemble à un sommet de l'autre ensemble.
Pour montrer que tout arbre est un graphe biparti, on peut utiliser l’induction sur le nombre de sommets de l’arbre.
Cas de base :un arbre avec un sommet est trivialement biparti.
Étape inductive :Supposons que tout arbre à n sommets soit biparti. Soit T un arbre à n+1 sommets. Nous pouvons construire un graphe biparti à partir de T en prenant un sommet comme une partie de la bipartition et les n sommets restants comme l'autre partie. Les arêtes du graphe biparti sont les mêmes que les arêtes de T.
Par récurrence, tout arbre est un graphe biparti.
