Let $G$ be a simple $4$-regular connected graph, and suppose that $G$ is planar and has $10$ faces. (A graph is $4$-regular if all of its vertices have degree $4$.)

  • Determine the number of edges of $G$.
  • Determine the number of vertices of $G$.

I know about the Euler's formula $n-m+f = 2$.

Therefore with $f = 10$ it can be rearranged to: $8= -n + m$.

However I am stuck as to continue to gain exact values for $n$ and $m$.


You have to use the fact that the graph is $4$ - regular, so all degrees of vertices are $4$.

Then, remember that the sum of all vertex degrees is closely connected (i.e. there exists a formula to connect them) to the number of edges.

Now, the sum of vertex degrees is simply $4\cdot n$, since you have $n$ vertices and each has degree $4$. Plugging this into the formula connecting vertex degrees with $m$ will give you one more equation for $m$ and $n$ next to the one you already have. Then, simply solve the system of equations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.