En el campo matemático de la teoría de grafos , el gráfico de la amistad (o gráfico del molino de viento holandés o n -fan ) F n es un gráfico plano , no dirigido, con 2 n + 1 vértices y 3 n aristas. [1]
El gráfico de amistad F n se puede construir uniendo n copias del gráfico de ciclo C 3 con un vértice común, que se convierte en un vértice universal para el gráfico. [2]
Por construcción, el gráfico de amistad F n es isomorfo al gráfico de molino de viento Wd(3, n ) . Es una distancia unitaria con circunferencia 3, diámetro 2 y radio 1. La gráfica F 2 es isomorfa a la gráfica de mariposa . Los gráficos de amistad se generalizan mediante los gráficos triangulares de cactus .
El teorema de la amistad de Paul Erdős , Alfréd Rényi y Vera T. Sós (1966) [3] establece que los grafos finitos con la propiedad de que cada dos vértices tienen exactamente un vecino en común son exactamente los grafos de la amistad. De manera informal, si un grupo de personas tiene la propiedad de que cada par de personas tiene exactamente un amigo en común, entonces debe haber una persona que sea amiga de todas las demás. Sin embargo, para gráficos infinitos, puede haber muchos gráficos diferentes con la misma cardinalidad que tengan esta propiedad. [4]
Mertzios y Unger dieron una prueba combinatoria del teorema de la amistad. [5] Craig Huneke proporcionó otra prueba. [6] Alexander van der Vekens informó sobre una prueba formalizada en Metamath en octubre de 2018 en la lista de correo de Metamath. [7]
La gráfica de la amistad tiene número cromático 3 y índice cromático 2 n . Su polinomio cromático se puede deducir del polinomio cromático del gráfico de ciclo C 3 y es igual a
El gráfico de amistad F n tiene bordes elegantes si y sólo si n es impar. Es elegante si y sólo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4) . [8] [9]
Cada gráfico de amistad tiene un factor crítico .
Según la teoría de grafos extremos , cada gráfico con suficientes aristas (en relación con su número de vértices) debe contener un abanico como subgrafo. Más específicamente, esto es cierto para un gráfico de vértices si el número de aristas es
donde es si es impar y es si es par. Estos límites generalizan el teorema de Turán sobre el número de aristas en un gráfico sin triángulos , y son los mejores límites posibles para este problema, en el sentido de que para cualquier número menor de aristas existen gráficos que no contienen un abanico. [10]
Dos vértices cualesquiera que tengan exactamente un vecino en común equivalen a que dos vértices cualesquiera estén conectados por exactamente un camino de longitud dos. Esto se ha generalizado a los gráficos, en los que dos vértices cualesquiera están conectados por un camino único de longitud . Porque no se conocen tales gráficos, y la afirmación de su inexistencia es la conjetura de Kotzig .