Results 1 to 2 of 2

Math Help - Question on planar graphs

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    1

    Question on planar graphs

    i'm stuck on this proof:
    prove that any planar graph with very vertex having degree 5 has at least 12 vertices.

    a planar graph G with all v vertices with degree 5 has 5v/2 edges
    Euler's formula states that vertices - edges + faces = 2
    so there are 3v/2 + 2 faces in G

    I'm not sure how to get the # of faces in G, or whether it's relevant to the problem.


    also this one:
    show that a plane graph with v>=3 vertices has at most 2v - 4 edges


    any help is appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by titandude21 View Post
    prove that any planar graph with very vertex having degree 5 has at least 12 vertices.

    a planar graph G with all v vertices with degree 5 has 5v/2 edges
    Euler's formula states that vertices - edges + faces = 2
    so there are 3v/2 + 2 faces in G

    I'm not sure how to get the # of faces in G, or whether it's relevant to the problem.
    Every face must have at least 3 edges, and each edge is shared between 2 faces. So 2\bigl(\tfrac{5v}2\bigr)\geqslant3\bigl(\tfrac{3v}  2+2\bigr).

    Quote Originally Posted by titandude21 View Post
    also this one:
    show that a plane graph with v>=3 vertices has at most 2v - 4 edges
    Not true. For example, the graph of a tetrahedron has 4 vertices and 6 edges (see attached image). What is true is that a plane graph with v\geqslant 3 vertices has at most 3v - 6 edges. The proof is the same as for the previous result: 2e\geqslant3f together with v+f=e+2.
    Attached Thumbnails Attached Thumbnails Question on planar graphs-g1_2.jpg  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Planar Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 15th 2011, 02:26 AM
  2. Planar graphs. Hint please :)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 17th 2010, 04:19 PM
  3. Planar graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 25th 2010, 10:18 PM
  4. Planar graphs
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: December 6th 2009, 07:13 AM
  5. Maximal planar graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 5th 2009, 08:36 AM

Search Tags


/mathhelpforum @mathhelpforum