Results 1 to 2 of 2

Math Help - Planar graphs

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    178

    Planar graphs

    Show that any graph having five or fewer vertices and a vertex of degree 2 is planar.

    I don't understand the question.

    Are they saying 5 or fewer vertices AND 1 vertex with a degree of 2?
    5 or fewer vertices with degrees of 2?

    Is it asking something else?

    If the first, could I put 3 vertices and one with a degree of 2?
    If the second, is that possible?

    Lastly, beyond drawing a graph, is there any way to show this?

    The answer is the back of the book is as follows:
    "a graph of five or fewer vertices and a vertex of degree 2 is homeomorphic to a graph with four or fewer vertices. Such a graph cannot contain a homeomorphic copy of K_{3,3}  or  K_{5} "




    Thanks!

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Are they saying 5 or fewer vertices AND 1 vertex with a degree of 2?
    Yes, I believe the assumption is saying that a graph has at most 5 vertices, one of which has degree 2.

    Let v be the vertex of degree 2, and let v1, v2 be the vertices it is connected to. The hint makes sense to me provided v1 and v2 are not connected: then v can be eliminated and an edge (v1, v2) can be added to create a homeomorphic graph. I am not sure how to proceed with the proof if v1, v2 are connected.
    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 Differential Geometry Forum
    Replies: 0
    Last Post: December 6th 2009, 07:13 AM
  4. Maximal planar graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 5th 2009, 08:36 AM
  5. Question on planar graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 8th 2009, 10:35 AM

Search Tags


/mathhelpforum @mathhelpforum