Polyhedral graphs with restricted number of faces of the same type (Q1349115)

A polyhedral graph is a planar and three-connected graph \(G=(V,E,F)\) with vertex set \(V\), edge set \(E\) and face set \(F\). A face \(\alpha \in F\) is an \(\langle a_1,\dots,a_l\rangle\)-face if \(\alpha\) is \(l\)-gon and the degrees of the vertices \(x_1,\dots,x_l\) incident with \(\alpha\) in cyclic order are \(a_1,\dots,a_l\), respectively. The type of a face \(\alpha \in F\) is the lexicographic minimum \(\langle b_1,\dots,b_l\rangle\) such that \(\alpha\) is an \(\langle b_1,\dots,b_l\rangle\)-face. A polyhedral graph \(G\) is called oblique if no two its faces are of the same type. Let \(z_{\langle b_1,\dots,b_l\rangle}\) be the number of faces of type \(\langle b_1,\dots,b_l\rangle\) in \(G\) and \(z\) be a positive integer. A polyhedral graph \(G\) is called \(z\)-oblique if \(z_{\langle b_1,\dots,b_l\rangle}\leq z\) for all types of faces of \(G\). The main result of the paper states that for each \(z\), the set of \(z\)-oblique graphs is finite. A consequence of this result is that for any positive integer there exists a polyhedral graph having at least \(k\) faces of the same type. The proof of the result is based on the discharging method.