Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

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

  1. #1
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    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 ...
    graph theory Planar graphs max number of edges and isomorphism-isomporphic_0.jpg
    Sorry I'm a bit uncertain
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    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!
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    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$.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

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

    Thanks SlipEternl
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory : coloring edges
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jan 28th 2011, 04:48 AM
  2. Replies: 5
    Last Post: Dec 22nd 2010, 01:42 AM
  3. Replies: 0
    Last Post: Apr 21st 2009, 09:43 AM
  4. Replies: 5
    Last Post: Jun 22nd 2008, 10:20 PM

/mathhelpforum @mathhelpforum