0

A plane connected graph has 22 corners (eng. Vertices) and all surfaces the graph divides the plane (also the external, unlimited surface) has just 4 edges

Find all possible values for the number of edges in the graph.

I get all surfaces to r = 4*e it is wrong how can i get the connection beetween surfaces and edges

user3704516
  • 407

1 Answers1

3

Let $V$ be the number of vertices, $F$ the number of faces and $E$ the number of edges of your graph. You have that $V = 22$ and condition that all faces have four edges can be translated into $2E = 4F$, since $4F$ counts every edge of your graph twice. Using Euler's relation, we get $$2 = V - E + F = 22 - E + \frac{E}{2} \ \implies \ E = 40.$$

D. Ungaretti
  • 2,668
  • How can you see that 2E = 4F – user3704516 Dec 09 '16 at 20:31
  • It is a double counting argument. Notice that every edge is part of exactly 2 faces. The number of elements of the set ${(e, f); e \in E, f \in F \ \text{and edge $e$ belongs to face $f$} }$ is by one side $2E$, since every edge belongs to exactly 2 faces, and by other side $4F$ since every face has four edges. – D. Ungaretti Dec 09 '16 at 20:58
  • Thanks David for that you answered my question evrything is clear now and Eulers relation is an standar! – user3704516 Dec 09 '16 at 21:08