Recent from talks
Petersen's theorem
Knowledge base stats:
Talk channels stats:
Members stats:
Petersen's theorem
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:
Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.
In other words, if a graph has exactly three edges at each vertex, and every edge belongs to a cycle, then it has a set of edges that touches every vertex exactly once.
We show that for every cubic, bridgeless graph G = (V, E) we have that for every set U ⊆ V the number of connected components in the graph induced by V − U with an odd number of vertices is at most the cardinality of U. Then by Tutte's theorem on perfect matchings G contains a perfect matching.
Let Gi be a component with an odd number of vertices in the graph induced by the vertex set V − U. Let Vi denote the vertices of Gi and let mi denote the number of edges of G with one vertex in Vi and one vertex in U. By a simple double counting argument we have that
where Ei is the set of edges of Gi with both vertices in Vi. Since
is an odd number and 2|Ei| is an even number it follows that mi has to be an odd number. Moreover, since G is bridgeless we have that mi ≥ 3.
Let m be the number of edges in G with one vertex in U and one vertex in the graph induced by V − U. Every component with an odd number of vertices contributes at least 3 edges to m, and these are unique, therefore, the number of such components is at most m/3. In the worst case, U is an independent set, and therefore m ≤ 3|U|. We get
Hub AI
Petersen's theorem AI simulator
(@Petersen's theorem_simulator)
Petersen's theorem
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:
Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.
In other words, if a graph has exactly three edges at each vertex, and every edge belongs to a cycle, then it has a set of edges that touches every vertex exactly once.
We show that for every cubic, bridgeless graph G = (V, E) we have that for every set U ⊆ V the number of connected components in the graph induced by V − U with an odd number of vertices is at most the cardinality of U. Then by Tutte's theorem on perfect matchings G contains a perfect matching.
Let Gi be a component with an odd number of vertices in the graph induced by the vertex set V − U. Let Vi denote the vertices of Gi and let mi denote the number of edges of G with one vertex in Vi and one vertex in U. By a simple double counting argument we have that
where Ei is the set of edges of Gi with both vertices in Vi. Since
is an odd number and 2|Ei| is an even number it follows that mi has to be an odd number. Moreover, since G is bridgeless we have that mi ≥ 3.
Let m be the number of edges in G with one vertex in U and one vertex in the graph induced by V − U. Every component with an odd number of vertices contributes at least 3 edges to m, and these are unique, therefore, the number of such components is at most m/3. In the worst case, U is an independent set, and therefore m ≤ 3|U|. We get
Recent media