0
$\begingroup$

I'm fighting with a homework question in Graph Theory. I think it requires Euler's formula. Can someone please give me a hand? I know the problem requires algebra, but I don't think it's that simple. Here is my question:

Let f be the number of faces in a plane diagram of a 3-regular connected planar graph. Let m and n be the number of edges and vertices, respectively. Find a formula for m in terms of n. Then find a formula for f in terms of n.

Euler's formula is: n-m+f = 2 where n = number of vertices, m = the number of edges, f = the number of faces.

Someone please help?

$\endgroup$
  • $\begingroup$ The answers I got to the questions were: Formula for m in terms of n: n-2+f=m. Formula for f in terms of n: 2-n+m=f. I know it's not that simple. $\endgroup$ – Tito Apr 16 '17 at 22:52
0
$\begingroup$

Use the fact that the graph is 3-regular to get a formula for m in terms of n. Use the degree-sum formula:

$$ \sum_{v \in V(G)} \deg(v) = 2 |E(G)|. $$

$\endgroup$

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.