Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- grafos:3regempper [2023/03/21 16:36] – edição externa 127.0.0.1
+++ grafos:3regempper [2023/05/05 12:59] (atual) – edição externa 127.0.0.1
@@ Linha 2: / Linha 2: @@
 <WRAP round box 100%>
-=== Corolário ===
+=== Corolário: Petersen $(1891)$ ===
 //Todo $3-$regular(**grafo cúbico**) sem [[.ponte | pontes]] admite emparelhamento perfeito.//
 </WRAP>
 <WRAP round box 100%>
+//**Demonstração:**//
 Temos que provar que qualquer grafo cúbico sem pontes $G=(V,E)$ satisfaz a condição de Tutte, ou seja, se encaixa no [[.teoempperfeito | Teorema do Emparelhamento Perfeito]]. Vamos fixar $S \subset V$ e $C$ uma componente conexa de tamanho impar de $G-S$.
-Como $G$ é um grafo cúbico, os graus (em $G$) dos vértices em $C$ somam um número ímpar(pois são ímpares os vérticesde grau $3$), mas apenas uma parte par dessa soma surge das arestas de $C$.
+Como $G$ é um grafo cúbico, os graus (em $G$) dos vértices em $C$ somam um número ímpar(pois são ímpares os vérticesde grau $3$), mas apenas uma parte par dessa soma surge das arestas de $C$. Portanto, $G$ tem um número ímpar de arestas $S-C$ e, portanto, possui pelo menos $3$ dessas arestas (uma vez que $G$ não possui pontes).
-Portanto, $G$ tem um número ímpar de arestas $S-C$ e, portanto, possui pelo menos $3$ dessas arestas (uma vez que $G$ não possui pontes).
+O número total de arestas entre $S$ e $G-S$ é, portanto, pelo menos $3q(G-S)$. Mas também é no máximo $3|S|$, porque $G$ é cúbico. Pelo Teorema do Emparelhamento Perfeito temos $q(G-S) \leq |S|$, logo temos um emparelhamento perfeito como requerido.
-O número total de arestas entre $S$ e $G-S$ é, portanto, pelo menos $3q(G-s)$. Mas também é no máximo $3|S|$, porque $G$ é cúbico. Daí $q(G-S) \leq |S|$, como requerido.
+<wrap right>$\square$</wrap>
+</WRAP>
-  *Assim a quantidade de arestas entre $G$ e $G\setminus S$ é pelo menos 3[[.compconexaimpar | $3q(G\setminus S)$]] e é no máximo $3|S|$, portanto pelo [[.teoempperfeito | teorema]] como temos que $q(G - S) \leq |S|$, temos um emparelhamento perfeito.
+----
+<WRAP round info>
+=== Referências ===
+  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch2.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 43. Acesso em 21/03/2023.
-<wrap right>$\square$</wrap>
 </WRAP>