Results 1 to 2 of 2

Thread: 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
    10
    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: Jun 15th 2011, 03:26 AM
  2. Planar graphs. Hint please :)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Nov 17th 2010, 05:19 PM
  3. Planar graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 25th 2010, 11:18 PM
  4. Planar graphs
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Dec 6th 2009, 08:13 AM
  5. Maximal planar graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 5th 2009, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum