[Math] Planar and Euler’s Formula Question

computer sciencediscrete mathematicsgraph theoryplanar-graphs

If a connected planar graph has four regions and six vertices, how many edges will the graph have?
(I believe the answer is 8 but I'm not positive)

1) 9

2) 8

3) 6

4) 7

Graph A = ({a,b,c,d,e,f,g}, {(a,d),(a,c),(a,b),(b,c),(e,f),(f,g),(e,g)})
Now consider the claim: A has two-regions.

1) False. Euler's formula is not valid because A is bipartite.

2) False. Euler's formula is not valid because A is not connected.

3) True, since there are 7 verts and 7 edges, the Euler formula yields: 7-7+|R| = 2; so |R|=2.

4) False. Euler's formula is not valid because A is not a planar graph.

Best Answer

Euler's formula states that a finite, connected, planar graph, when drawn in the plane with no intersecting edges, satisfies:

$$v-e+f=2$$

where $v$ is the number of vertices, $e$ the number of edges, and $f$ the numbers of faces/regions.

  1. substitute into the formula. That's all.

  2. Draw that graph on paper. The definition has nothing to do with bipartiteness, so that rules out 1). Is it planar and connected? If not, the answer is 2) or 4). Otherwise, the answer is 3).

Related Question