Finding the number of vertices, edges and faces given structure.
Matthew Harrington 
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:
- Each vertex has degree five.
- Each face is either a triangle or a pentagon.
- Each pentagon shares edges with five triangles.
- Triangles are divided into Type I: sharing edges with one pentagon and two triangles, and Type II: sharing edges with three triangles.
- 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.
$\endgroup$1 Answer
$\begingroup$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$.
$\endgroup$ 6
