Mostrar páginaRevisões anterioresLinks reversosVoltar ao topo 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> grafos/3regempper.txt Última modificação: 2023/05/05 12:59por 127.0.0.1