A connected planar graph has 26 faces and an unknown amount of vertices (denoted as "V"). All the vertices have the same degree. What are all possible values of V?
What I have so far:
V + F = E + 2 (Euler) –>
V + 26 = E + 2 –>
V -E = -24
I randomly tested these out for different values of degree.
Every vertex has degree 3, V = 48
Every vertex has degree 4, V = 24
Every vertex has degree 5, V = 16
Every vertex has degree 6, V = 12
Which of these cases can be realized? V = 12, 16, 24, 48? Did I miss anything? I noticed that as the degree increases, the value for V decreases as well (so I doubt that there will be any integer values after V = 12).
Best Answer
Case 1: degree 3. We construct a sequence of graphs with only ``triangular'' faces. Let $G_0$ be a triangle, it has 3 vertices and 2 triangular faces. Having constructed $G_n$, we take an arbitrary triangular face, add a vertex in the middle and connect it to the three corners of the triangle. This procedure adds 1 vertex and 2 faces. We conclude that $G_{23}$ has $3+23=26$ vertices and $2+46=48$ triangular faces. The dual of this graph has 26 faces, and 48 vertices of degree 3. Note that this produces many realizations, since there are many ways to choose the face for the next step.
Case 2: degree 4. We construct a sequence of graphs with only faces of length 4. Start with a 6-cycle, draw a chord between two opposite vertices on the inside and another one on the outside. Call this graph $G_0$, it has 6 vertices and 4 faces of length 4. Having constructed $G_n$, we take an arbitrary face and replace it with a copy of $G_0$. This adds 2 vertices and 2 faces. We conclude that $G_{10}$ has $6+20=26$ vertices and $4+20=24$ faces. The dual of this graph has 26 faces, and 24 vertices of degree 4. Again: this produces many realizations.
Case 3: degree 5. Start with a octahedron, call two independent vertices the poles and the remaining 4-cycle the equator. You have 6 vertices and 8 faces. Subdivide every edge along the equator and draw 8 new edges from the 4 new vertices to the 2 poles. You now have 10 vertices and 16 faces. Add two new vertices to each of the 8 new edges you created in the previous step. You now have 26 vertices and 16 faces, each of them has length 5. The dual of this graph has 26 faces, and 16 vertices of degree 5.
Case 4: degree >5. This is impossible. Every planar graph has a vertex of degree at most 5.