9 votos

Un grafo 3-regular con menos de 3 puentes tiene una coincidencia perfecta

He estado tratando de aprender algo de teoría de grafos en mi cuenta y me he encontrado con esta declaración, pero ninguna prueba. Al parecer es llamado Petersen del teorema, pero cuando vi que hasta para una prueba, sólo se demuestra en el caso de que no bridgess.

He estado tratando de averiguar cómo probar esta versión de la declaración, pero estoy bastante atascado. Los punteros se agradece. Estoy pensando Tutte del teorema es la manera de ir sobre la base de la prueba de la bridgeless caso, pero no veo cómo hacerlo cuando no bridgeless.

9voto

Keltia Puntos 8104

Deje $\mathrm{odd}(H)$ denotar el número impar de componentes de la gráfica de $H$.

Deje $G$ ser conectado cúbicos gráfico con no más de dos de corte de los bordes. Asumir por medio de la contradicción que $G$ no tiene perfecto maridaje.

Dado que el número de vértices de $G$ es aún, si $G$ no tiene perfecto maridaje, a continuación, un tamaño máximo de coincidencia en $G$ debe faltar al menos dos vértices y así, por el teorema de Tutte-Berge teorema, existe un subconjunto $S$ $V(G)$ tal que $|S|\le\mathrm{odd}(G\setminus S)-2$. Cada componente impar de $G\setminus S$ tiene un número impar de vértices, incluso de grado y por lo tanto cada componente impar de $G\setminus S$ está unido a $S$ por un número impar de aristas. Si este número impar es uno, el correspondiente borde debe ser un corte-borde. Por nuestra hipótesis es la siguiente todos, pero en la mayoría de los dos componentes de $G\setminus S$ se unió a $S$ por al menos tres aristas, de ahí el extraño componentes se unen a $S$ por lo menos $$ 3(\mathrm{impar}(G\setminus S)-2)+2\ge3|S|+2 $$ los bordes. Pero el número de aristas en $G$ terminando en los vértices de $S$ es en la mayoría de los $3|S|$, y hemos llegado a una contradicción.

Observación: El Tutte-Berge teorema afirma que el número de vértices no están cubiertos por una coincidencia de tamaño máximo es de $\max_{S\subseteq V(G)}\{\mathrm{odd}(G\setminus S)-|S|\}$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X