Polyhedral graphs with extreme numbers of types of faces Original Research Article

A face α∈F of a polyhedral graph G(V,E,F) is an 〈a1,a2,…,al〉-face if α is an l-gon and the degrees d(xi) of the vertices xi∈V incident with α in the cyclic order are ai,i=1,2,…,l. The lexicographic minimum 〈b1,b2,…,bl〉 such that α is a 〈b1,b2,…,bl〉-face is the type of α. All polyhedral graphs having only one type of faces are listed. It is proved that the set of triangulations having only faces of different types is non-empty and finite.