Math 2.0

Combinatorics Matchings and covers Theorem

Tutte's theorem

Builds on Connected componentPerfect matching

Statement

Let GG be a finite graph with vertex set VV. For U⊆VU \subseteq V, let o(G−U)o(G - U) be the number of connected components of G−UG - U with an odd number of vertices. Then GG has a perfect matching if and only if o(G−U)≤∣U∣o(G - U) \le |U| for every U⊆VU \subseteq V.

Remarks

The condition is necessary. In a perfect matching, each odd component of G−UG - U has a vertex that is matched to a vertex of UU. These vertices of UU are distinct. For U=∅U = \varnothing, the condition says that each component of GG has an even number of vertices. The theorem is a special case of the Tutte–Berge formula for the size of a maximum matching.

History

The theorem is named after William Thomas Tutte.

Reading path

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

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionMatching, definition, no evidence levelMatchingdefinitionWalk, definition, no evidence levelWalkdefinitionPerfect matching, definition, no evidence levelPerfect matchingdefinitionReachability, definition, no evidence levelReachabilitydefinitionConnected component, definition, no evidence levelConnected componentdefinitionTutte's theorem, statement, no evidence levelTutte's theoremstatement
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. Graph definition
  2. Matching definition
  3. Walk definition
  4. Perfect matching definition
  5. Reachability definition
  6. Connected component definition
  7. Tutte's theorem statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Tutte's_theorem_on_perfect_matchings, Tutte's theorem
About this page
Tag08J7R35B6Q
URIm2://08J7R35B6Q
Kindstatement, theorem
WritingW1 stated
MSC05C70
StatusThis copy of the site has no build data. Run m2 status 08J7R35B6Q.
UsesConnected component, Perfect matching
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

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

What links here

Used by