grafos:3regempper [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

===== Cubos e Emparelhamento Perfeito =====

<WRAP round box 100%>
=== 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$. 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.

<wrap right>$\square$</wrap>
</WRAP>

----

<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>