# Thread: graph theory Planar graphs max number of edges and isomorphism

1. ## graph theory Planar graphs max number of edges and isomorphism

Q:What is the maximum number of edges in a simple, planar graph on 7 vertices?
Drawtwo nonisomophic simple, planar graphs on 7 vertices that have this many edges
. Clearlystate why your graphs are not isomorphic.
A: For the first part I got 11 edges
The second part with the Planar graphs I understand that the edges can't cross...I drew these but I think that is wrong...
The graphs are not isomorphic because elements in the graph share different degrees ...

Sorry I'm a bit uncertain

2. ## Re: graph theory Planar graphs max number of edges and isomorphism

For A, you can draw MANY more edges. You are supposed to have two planar graphs with the maximum number of edges.

Here are some that you can add and it will still be a planar graph: (2,4), (4,5), (5,6), (6,7), (7,1), (1,4), (1,5), (1,6). That is at least 8 additional edges you can add just by a quick glance. That is a total of at least 15 edges. Is it possible to have more than 15? Possibly. It is easy to show that for a simple planar graph on $n$ vertices, $4n-8$ is an upper bound for the number of edges of the graph (I will leave this to you to verify). But, is it possible to draw a simple planar graph on 7 vertices with $4\cdot 7-8 = 20$ edges? Try it!

3. ## Re: graph theory Planar graphs max number of edges and isomorphism

Wow...It's true to say at this point I suck at this I'll get to work on it and try it ,
Thanks a million
Cheers

4. ## Re: graph theory Planar graphs max number of edges and isomorphism

Actually, we know by Euler's formula, $v-e+f=2$, so $e=f+5$. Because every face is bounded by at least 3 edges and every edge is incident to exactly two faces, we have that the maximum number of edges $e\le 3v-6 = 3\cdot 7-6 = 15$.

5. ## Re: graph theory Planar graphs max number of edges and isomorphism

Thanks SlipEternl