¿Cuáles son los resultados más importantes de la teoría de grafos?

Question

¿Cuáles son los teoremas/resultados/resultados ampliamente aplicables en la teoría de grafos que todo el mundo debería conocer?

Answer 1

Fórmula de Euler $V - E + F = 1$ para los grafos planos es extremadamente importante; en cierto sentido, motivó gran parte de la topología moderna. (Una excelente introducción a esta tesis es el libro de Richeson Gema de Euler .) También conduce a una prueba razonablemente corta de la clasificación de los sólidos platónicos, así que incluso antes de la generalización, es bastante importante. La generalización a los grafos sobre superficies se utiliza para demostrar la fácil dirección de la Conjetura de Heawood .

Por supuesto, hoy en día se reconoce que la fórmula de Euler es realmente una afirmación sobre triangulaciones de la esfera, y la generalización a las triangulaciones de variedades arbitrarias y otras caracterizaciones de la característica de Euler es fundamental.

El Geometry Junkyard tiene una buena lista de diecinueve pruebas de la fórmula de Euler . Uno de ellos utiliza otro hecho básico y útil sobre los gráficos, que es que siempre tienen árboles de distribución . Esto se utiliza, por ejemplo, en topología para demostrar que la realización geométrica de un grafo es homotópicamente equivalente a una cuña de círculos, lo que demuestra que los subgrupos de grupos libres son libres.

Answer 2

Teoremas de Kuratowski y Wagner que dan las condiciones necesarias y suficientes para que un grafo finito sea planar.

Debo añadir que ciertamente es posible argumentar que estos son en realidad teoremas de topología más que de teoría de grafos.

Para una prueba sencilla de la no planitud de $K_{3,3}$ y $K_5$ se puede consultar la obra de Munkres Topología 2ª ed. §64 y al final de la sección señala "Es un teorema notable, debido a Kuratowski, que la inversa también es verdadera. La demostración no es fácil".

Answer 3

Teorema del matrimonio de Hall es ampliamente aplicable. Sorprendentemente, resulta ser equivalente a otros teoremas de la teoría de grafos y la combinatoria que también son ampliamente aplicables:

• Teorema de Konig
• Teorema de Menger
• Flujo máximo de corte mínimo
• El Teorema de Birkhoff-von Neumann
• Teorema de Dilworth