¿Puede haber una $4$ -¿Gráfico regular con exactamente una coincidencia perfecta? Es decir, un grafo que tiene un emparejamiento perfecto, pero no dos emparejamientos perfectos (no necesariamente disjuntos).
Basado en un resultado bien conocido debido a Kotzig, un grafo con un emparejamiento perfecto único tiene una arista de corte (véase por ejemplo el libro: Matching Theory de Lovasz y Plummer). Pero un grafo 4 regular no puede tener una arista de corte, por lo que no puede tener un emparejamiento perfecto único.
Me gustaría secundar esta respuesta. El argumento es correcto. Lo de "un grafo 4 regular no puede tener una arista cortada" se sostiene de forma más general: 'cualquier grafo regular conectado no tiene una arista cortada'. Esto se deduce fácilmente sumando grados.
EDIT 2020-04-13: esta sugerencia de cómo dar una prueba más fácil es errónea. Lo siento. Lo dejaré arriba ya que puede ser interesante no obstante. Tacharé la afirmación errónea. (Por supuesto, evidentemente, los grafos 3 regulares pueden contener un puente. Mis disculpas).
Ghodrati ya ha dado una prueba correcta. Vale la pena señalar
también es posible deducirlo del clásico de Petersen teorema en que todo grafo cúbico sin puente tiene una correspondencia perfecta.
(Podría decirse que esto es más ligero herramienta que el teorema de Kotzig utilizado por Ghodrati; esa es la razón principal por la que hago esta observación).
Para ver esto, basta con observar que si hubiera un $4$ -regular con un único emparejamiento perfecto, entonces la eliminación de este emparejamiento dejaría un $3$ -regular sin un emparejamiento perfecto; por el teorema de Petersen, tendría que tener un puente; pero un $3$ -el gráfico regular obviamente no puede tener ningún puente, como se ve fácilmente sumando grados. Esto demuestra que un $4$ -grafo regular con un único emparejamiento perfecto es imposible.
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.
1 votos
Si un grafo 4-regular tiene exactamente un emparejamiento perfecto, la eliminación de las aristas de ese emparejamiento debería dejar un 3-regular sin emparejamiento perfecto. Probablemente se pueden añadir cuidadosamente aristas a este gráfico de tal manera que se crea exactamente una coincidencia perfecta.
0 votos
Casi me he convencido de que no se puede obtener el grafo deseado añadiendo aristas al grafo 3-regular que he enlazado. Siempre te ves obligado a poner una arista entre los "grupos" de vértices, y eso parece romper el ejemplo.
1 votos
@AustinMohr He llegado a la misma conclusión. Sospecho que la respuesta a mi pregunta es negativa. Sólo que no puedo componer una prueba para mi conjetura.