Grafo de la amistad

[1]​ El grafo de la amistad Fn puede ser formado construyendo n copias del ciclo C3 con un vértice común.

[2]​ Por construcción, el grafo de la amistad Fn es isomorfo al grafo molino de viento Wd(3,n).

Y el grafo F2 es isomorfo al grafo mariposa El teorema de la amistad de Paul Erdős, Alfréd Rényi, y Vera T. Sós de 1966[3]​ establece que los grafos finitos con la propiedad que cada dos vértices tengan exactamente un vecino en común son los grafos de la amistad.

Informalmente, si un grupo de personas tiene la propiedad que cada par de ellos tienen exactamente un amigo en común, entonces debe haber una persona que sea amigo con todos los demás.

Su polinomio cromático puede ser deducido del polinomio cromático del ciclo C3 y es igual a