Math 2.0

statement proposition

Trees are bipartite

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.

Explanations

L1 human

Colour the vertices of a tree by levels, from a chosen root: even levels white, odd levels black. Each edge goes between neighbouring levels, so it joins a white vertex and a black vertex.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 11 nodes in this order. The foundations come first, and the list ends with this node.

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 node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • 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

Sources

  1. Web https://en.wikipedia.org/wiki/Bipartite_graph, Examples

What links here

No node links to this node yet.