Number of Vertices of a connect planer graph with 100 edges

Question

Assume $G$ is a connected planar graph with 100 edges. While the edges can be split into two sets, $S_1$ and $S_2$ such that $|S_1|=60$ and $|S_2|=40$. Given that for all $e$ in $S_1$, the face on one side of $e$ has 3 edges, and the face on the other side has 10 edges. Also, for all $e$ in $S_2$, the two faces on each side of $e$ are distinct from each other and both have 10 edges.

Then, How many vertices does G have?

I guess this question can be solved by Euler's formula in planar graph that $"V-E+F=2"$. However, I do not know how to calculate the number of faces in the graph.

Anyone can give me some hints for solving this questions? Thanks!

Answer 1

• Because the edges in $S_1$ and $S_2$ are disjoint, and there are $100$ edges in total, we know that every edge is in either $S_1$ or $S_2$.
• Thus every face is either of degree $3$ or degree $10$.
• We can consider splitting each edge into two sides, one for each face it touches. You can think of this as cutting the plane up into pieces along the edges. Each side is the resulting boundary segment of one of the faces.
• Each side is in contact with exactly one face, so a face of degree $3$ has $3$ sides unique to it, and each face of degree $10$ has $10$ sides unique to it.
• Each edge in $S_1$ has two sides, one of which is for a degree $3$ face, and the other for a degree $10$ face. Since there are $60$ edges in $S_1$ that provides $60$ degree-$3$ sides and $60$ degree-$10$ sides.
• Each edge in $S_2$ has two degree-$10$ sides. Since there are $40$ edges, that provides $80$ degree-$10$ sides.

Altogether, there are $60$ degree-$3$ sides and $60 + 80 = 140$ degree-$10$ sides. Now as each degree-$3$ face is surrounded by $3$ degree-$3$ sides, there has to be $20$ of them. And each degree-$10$ face is surrounded by $10$ degree-$10$ sides, so there has to be $14$ of them.

Hence your graph has a total of $34$ faces, and $2+100 - 34 = 68$ vertices.