Sim, toda árvore é um gráfico bipartido.

Uma árvore é um grafo conectado sem ciclos. Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos, de modo que cada aresta conecte um vértice de um conjunto a um vértice do outro conjunto.

Para mostrar que toda árvore é um grafo bipartido, podemos usar a indução no número de vértices da árvore.

Caso base:Uma árvore com um vértice é trivialmente bipartida.

Etapa indutiva:suponha que toda árvore com n vértices seja bipartida. Seja T uma árvore com n+1 vértices. Podemos construir um grafo bipartido a partir de T tomando um vértice como uma parte da bipartição e os n vértices restantes como a outra parte. As arestas do grafo bipartido são iguais às arestas de T.

Por indução, toda árvore é um grafo bipartido.