Petersen theorem

Every finite , 3-regular (http://planetmath.org/Valency), 2-edge connected graph has a complete matching.

Proof.

Using the notations from the Tutte theorem, we have to prove that for all $X\\subseteq V(G)$ the inequality $c_{p}(G-X)\\leq|X|$ holds. There are at least $3$ edges running between $X$ and an odd component of $G-X$ : there cannot be one edge, since $G$ is 2-edge connected, and there also cannot be two edges, because three edges start from all vertices of an odd component, so the number of edges leaving an odd component is odd. Let $t$ be the number of all edges between $X$ and the odd components of $G-X$ . Now we have $t\\geq 3c_{p}(G-X)$ . But $G$ is 3-regular, thus $t\\leq 3|X|$ . This gives $c_{p}(G-X)\\leq|X|$ .∎

单词	PetersenTheorem
释义	Petersen theorem Every finite , 3-regular (http://planetmath.org/Valency), 2-edge connected graph has a complete matching. Proof. Using the notations from the Tutte theorem, we have to prove that for all $X\\subseteq V(G)$ the inequality $c_{p}(G-X)\\leq\|X\|$ holds. There are at least $3$ edges running between $X$ and an odd component of $G-X$ : there cannot be one edge, since $G$ is 2-edge connected, and there also cannot be two edges, because three edges start from all vertices of an odd component, so the number of edges leaving an odd component is odd. Let $t$ be the number of all edges between $X$ and the odd components of $G-X$ . Now we have $t\\geq 3c_{p}(G-X)$ . But $G$ is 3-regular, thus $t\\leq 3\|X\|$ . This gives $c_{p}(G-X)\\leq\|X\|$ .∎
随便看	Gergonne point GergonneTriangle Gergonne triangle Germ germ GermOfSmoothFunctions germ of smooth functions GermSpace germ space GershgorinsCircleTheorem GershgorinsCircleTheoremResult Gershgorin’s circle theorem Gershgorin’s circle theorem result GerstenhaberSerezhkinTheorem Gerstenhaber - Serezhkin theorem GertrudeBlanch Gertrude Blanch GertrudeCox Gertrude Cox Getting started GettingTaylorSeriesFromDifferentialEquation getting Taylor series from differential equation Girth girth GiugaNumber