Theorem

Petersen's Theorem

Combinatorics and Graph Theory

Petersen's Theorem states that every bridgeless graph in which each vertex has exactly three edges, called a cubic graph, has a perfect matching, meaning a set of edges pairing up all its vertices with none left out and none shared between two pairs. Named for Julius Petersen, it was one of the earliest results of graph theory and was later strengthened to show that every such graph in fact decomposes into a perfect matching together with a collection of disjoint cycles covering the remaining edges.

Facts

Classification

Statement Form

Existence Theorem 1

Statement

Every cubic, bridgeless graph contains a perfect matching. 1

Connections

Has Statement Form

Existence Theorem

In Branch

Graph Theory

Source Petersen's theorem (Wikipedia)

Proved By

Julius Petersen

Source Petersen's theorem (Wikipedia)

Sources

1. Petersen's theorem (Wikipedia)

Introduction
Every cubic, bridgeless graph contains a perfect matching.
In Branch: Graph Theory, Lead sentence
In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in
Proved By: Julius Petersen, Lead paragraph
In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:
In Group: Graph Theory, Lead section
In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen

Switch Atlas

The Inner World

The Civil World

The Natural World

Petersen's Theorem

Has Statement Form

In Branch

Proved By