# Graph Theory - To Euler or not to Euler? With attempted working.

• Feb 20th 2010, 09:26 AM
novembersquared
Graph Theory - To Euler or not to Euler? With attempted working.
I'm having a bit of difficulty with this question. I have posted part of my working (though it may be completely wrong) below. I'm assuming I need to use Euler's formula.

Find an upper bound on the number of edges of a connected simple plane graph with number of vertices - n (greater than or equal to) 3 and girth - g (greater than or equal to) 3. Use this to show that the Petersen graph is non-planar.

m= no. of edges
n= no. of vertices
L= no. of faces

From the question we know that each face is bounded by at least 3 edges and each edge seperates 2 faces.

Therefore: m (is greater than or equal to) 3L/2

Combining with Euler's formula: n - m + L = 2

We get m (is less than or equal to) 3n - 6.

This is what I believe is the upper bound. By plugging in the values for the Petersen graph (n=10, m=15) I was hoping to get a false inequality to show that the graph is in fact non-planar. However the petersen graph passes this 'test'.

So I was wondering if my initial upperbound is wrong, or if that is not the correct way to prove the petersen graph is non-planar.

Any help would be appreciated. Thanks