Un árbol es un gráfico conexo sin ciclos. Un gráfico bipartito es un gráfico cuyos vértices se pueden dividir en dos conjuntos disjuntos de modo que cada arista conecta un vértice de un conjunto con un vértice del otro conjunto.
Para demostrar que cada árbol es un gráfico bipartito, podemos usar la inducción sobre el número de vértices del árbol.
Caso base:un árbol con un vértice es trivialmente bipartito.
Paso inductivo:suponga que todo árbol con n vértices es bipartito. Sea T un árbol con n+1 vértices. Podemos construir un gráfico bipartito a partir de T tomando un vértice como parte de la bipartición y los n vértices restantes como la otra parte. Las aristas del gráfico bipartito son las mismas que las aristas de T.
Por inducción, todo árbol es un grafo bipartito.
