2
$\begingroup$

A plane graph $G$ has 7 faces: 3 triangles, 3 quadrilaterals and 1 pentagon. How many edges and vertices does it have?

How this task should be solved? I came up with nothing better, than just manually drawing it and counting edges/vertices. From here, of course, I have no chance to prove that there is no other solution.

enter image description here

$\endgroup$
5
  • 2
    $\begingroup$ Hint: Every edge belongs to two faces, so count the edges in all the faces and adjust. Then use Euler's formula to find the number of vertices. $\endgroup$
    – hardmath
    Mar 8, 2017 at 12:48
  • $\begingroup$ Is the hint correct? Border edges do not need to belong to 2 faces. However, I'm also missing the pentagon, so my understanding of plane graph may be wrong. $\endgroup$
    – Pieter21
    Mar 8, 2017 at 13:05
  • $\begingroup$ And for Euler to be unique, the graph has to be connected. Was that given? $\endgroup$
    – Pieter21
    Mar 8, 2017 at 13:11
  • $\begingroup$ What would your answer be for two triangles? They can be disconnected, share a vertex and share an edge, all giving different answers. $\endgroup$
    – Pieter21
    Mar 8, 2017 at 13:17
  • $\begingroup$ @Pieter21: The unbounded face (exterior face) counts for the purpose of Euler's formula and should be counted for the sake of having every edge belong to two faces. The Question claims one pentagon, and in the illustration this pentagon is the unbounded face. Your concern about uniqueness may be related to various ways of embedding a graph in the plane, but this does not change the number of edges or vertices. $\endgroup$
    – hardmath
    Mar 8, 2017 at 13:43

1 Answer 1

Reset to default
1
$\begingroup$

Using @hardmath hint in comments, the solution is very straightforward:

  1. 3 triangles, 3 quadrilaterals and 1 pentagon gives us 26 sides. Each side must be some edge. Each edge must belong precisely to 2 faces. So we have $26/2 = 13$ edges.

  2. Using Euler's formula we see that $v + 7 - 13 = 2 \Rightarrow v = 8$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .