Euler\'s formula for planar graphs states: Let G be a plane drawing of a connect

Question

Euler's formula for planar graphs states:

Let G be a plane drawing of a connected planar graph, and let n, m, and f be the number of vertices, edges, and faces (respectively) of G. Then ...

Which of the following combinations of vertices, edges, and faces are possible for a connected planar graph drawn on a plane?

There are 3 correct answers out of 5.

A. n = 12
m = 10
f = 0

B. n = 12
m = 12
f = 2

C. n = 12
m = 14
f = 4

D. n = 12
m = 22
f = 12

E. n = 12
m = 12
f = 4

A. n = 12
m = 10
f = 0

B. n = 12
m = 12
f = 2

C. n = 12
m = 14
f = 4

D. n = 12
m = 22
f = 12

E. n = 12
m = 12
f = 4

Explanation / Answer

Euler's formula for connected planar graphs states that

n-m+f=2

Where n, m and f are vertices , edges and faces respectively.

(A)

Planar graphs with 0 faces is not possible.

So it is not write however it satisfy n-m+f=2

But it is not correct.

(B)

12-12+2=2

It satisfies Euler's rule hence it is correct.

(C)

12-14+4=2

It satisfies Euler's rule hence it is correct.

(D)

12-22+12=2

It satisfies Euler's rule hence it is correct.

(E)

12-12+4=4

It does not satisfy Euler's rule hence it is not correct.

Thus,

Only B,C and D are correct.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.