Math 2.0

Combinatorics Proof

Proof that trees are bipartite

Builds on TreeAcyclic graphBipartite graphA graph is bipartite iff it has no odd cycle

Proof

  1. A tree TT is acyclic, so it has no cycle at all.
  2. In particular, TT has no cycle of odd length.
  3. By the theorem that a graph is bipartite iff it has no odd cycle, TT is bipartite.

Idea

The only obstruction to splitting the vertices into two sides is an odd cycle. A tree has no cycles, so nothing can go wrong. Concretely, colour each vertex by the parity of its distance to a fixed root.

Reading path

To understand this page from the ground up, read these 45 pages in order. The foundations come first. The path takes the proofs Proof that a graph is bipartite iff it has no odd cycle, Proof of strong induction from ordinary induction.

  1. Bipartite graph definition
  2. Definition by recursion concept
  3. Element definition
  4. Graph definition
  5. Mathematical induction concept
  6. Natural numbers object
  7. Peano axioms concept
  8. Proposition concept
  9. Set definition
  10. Walk definition
  11. Successor function definition
  12. Disjunction definition
  13. Implication definition
  14. Predicate definition
  15. Family of sets definition
  16. Ordered pair definition
  17. Reachability definition
  18. Trail definition
  19. Union definition
  20. Addition of natural numbers definition
  21. The successor function is injective statement
  22. Zero is not a successor statement
  23. Existential quantifier definition
  24. Universal quantifier definition
  25. Cartesian product definition
  26. Distance in a graph definition
  27. Connected component definition
  28. Connected graph definition
  29. Circuit definition
  30. Subset definition
  31. Union of a family of sets definition
  32. Order on the natural numbers definition
  33. Uniqueness quantifier definition
  34. Binary relation definition
  35. Cycle definition
  36. Proof of strong induction from ordinary induction proof
  37. Acyclic graph definition
  38. Function definition
  39. Strong induction statement
  40. Tree definition
  41. Choice function definition
  42. Axiom of choice statement
  43. Proof that a graph is bipartite iff it has no odd cycle proof
  44. A graph is bipartite iff it has no odd cycle statement
  45. Proof that trees are bipartite proof

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Bipartite_graph, Examples
About this page
TagKRHWPPEZZ5
URIm2://KRHWPPEZZ5
Kindproof
WritingW0 stub
MSC05C05
ProvesTrees are bipartite
UsesTree, Acyclic graph, Bipartite graph, A graph is bipartite iff it has no odd cycle
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.