Math 2.0

Combinatorics Proposition

Trees are bipartite

Builds on TreeBipartite graph

Statement

Let TT be a tree. Then TT is bipartite.

Remarks

Proof: fix a vertex rr. Put a vertex in AA if its distance to rr is even, and in BB if it is odd. The ends of an edge have distances that differ by 11. It also follows from the theorem that a graph is bipartite iff it has no odd cycle, because a tree has no cycle at all.

Reading path

To understand this page from the ground up, read these 11 pages in order. The foundations come first.

Show the path as a graph
Bipartite graph, definition, no evidence levelBipartite graphdefinitionGraph, definition, no evidence levelGraphdefinitionWalk, definition, no evidence levelWalkdefinitionReachability, definition, no evidence levelReachabilitydefinitionTrail, definition, no evidence levelTraildefinitionConnected graph, definition, no evidence levelConnected graphdefinitionCircuit, definition, no evidence levelCircuitdefinitionCycle, definition, no evidence levelCycledefinitionAcyclic graph, definition, no evidence levelAcyclic graphdefinitionTree, definition, no evidence levelTreedefinitionTrees are bipartite, statement, no evidence levelTrees are bipartitestatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Bipartite graph definition
  2. Graph definition
  3. Walk definition
  4. Reachability definition
  5. Trail definition
  6. Connected graph definition
  7. Circuit definition
  8. Cycle definition
  9. Acyclic graph definition
  10. Tree definition
  11. Trees are bipartite statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Bipartite_graph, Examples
About this page
Tag0BN2A6EBYA
URIm2://0BN2A6EBYA
Kindstatement, proposition
WritingW0 stub
MSC05C05
StatusThis copy of the site has no build data. Run m2 status 0BN2A6EBYA.
UsesTree, Bipartite graph

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.