Finding the number of vertices, edges and faces given structure.

Question

I am new to graph theory and I would like to have some insight into a method on how to solve questions like this.

Given a simple planar graph in a sphere satisfying the conditions that:

1. Each vertex has degree five.
2. Each face is either a triangle or a pentagon.
3. Each pentagon shares edges with five triangles.
4. Triangles are divided into Type I: sharing edges with one pentagon and two triangles, and Type II: sharing edges with three triangles.
5. Each Type I triangle shares edges with one pentagon and two Type II triangles, and each Type II triangle shares edges with one Type I triangle and two Type II triangles.

Find the number of vertices, edges, and faces respectively for the graph.

Answer 1

Define the number of vertices, edges, faces to be $V,E,F$. We can further split $F=P+T$, where $P$ is the number of pentagons and $T$ the number of triangles, and further still $T=T_1+T_2$ where $T_1$ is the number of triangles of type I and $T_2$ the number of type II.

There are three equations we can get using common, textbook arguments and $(1),(2)$:

• Euler's formula says $V-E+F=2$.
• If you sum all the vertex degrees you double-count each edge, so $2E=5V$.
• Summing edge counts of all faces again double-counts edges, so $2E=5P+3T$.

Solve for $E$ then $V$ in terms of $P,T$, plug into Euler's, get a linear equation in $P,T$.

Similar logic can be used with conditions $(3),(4),(5)$:

• Since type II triangles are not incident to pentagons, each pentagon is incident to $5$ type I triangles; use this to triple-count type I triangles in terms of $P$ and $T_2$.

• Similarly, we can triple-count type II triangles in terms of $T_1$ and $T_2$.

Use the latter to find a nice relationship between $T_1,T_2$ and plug into the former to relate to $P$, then go back to readdress the original linear equation involving $P$ and $T$.