Using Euler's formula and the Handshake Theorem, how can I show that this graph is non-planar?

Printable View

- May 16th 2006, 09:08 AMNatasha1Euler's formula + Handshake Theorem
Using Euler's formula and the Handshake Theorem, how can I show that this graph is non-planar?

- May 16th 2006, 04:31 PMThePerfectHacker
The number of vertices is 8

The number of edges is 14

The number of faces is f

Then, 8-14+f=2 if planar.

Thus,

f=8

Which is not true.

I did it this way because I was too lazy counting all the faces. - May 17th 2006, 08:58 AMNatasha1
I actually counted 21 edges, am I wrong?

Euler's formula states that v+f = e+2

Here

v=8

e=21

f=?

so 8+f=21+2

f=15 which is not true as there are many more. Hence the graph is non-planar.

Using the Handshake Theorem that states that 2e >= 3f

we get ( 2(21) )/ 3 >= f which gives f <= 14 which again is not true, hence the graph is non-planar.

Am I correct?