Results 1 to 7 of 7

Math Help - Planar graphs. Hint please :)

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    13

    Planar graphs. Hint please :)

    Is there a connected planar (simple) graph such that:
    (a) each vertex has degree 4?

    Havn't done decision maths in a while and googles not much help.(or maybe im not looking very well!)

    Just need a hint really if you can. .

    Im tempted to say there is not...but im not sure if im meant to use an algorithm or some equation to show such...

    Thank-yous
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32
    Hint: Recall bipartite graphs, where you have two sets of verticies X and Y, where the verticies of X are only connected to vertices of Y and vice-versa. Which values of X and Y would you choose such that each vertex has degree 4?

    sadly, don't think there's an algorithm to always find such graphs. however, the Handshaking Lemma can be useful for showing that some graphs can't exist. (if the sum of the degrees of each vertex is an odd number... what can we conclude?)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    13
    Quote Originally Posted by MacstersUndead View Post
    Hint: Recall bipartite graphs, where you have two sets of verticies X and Y, where the verticies of X are only connected to vertices of Y and vice-versa. Which values of X and Y would you choose such that each vertex has degree 4?

    sadly, don't think there's an algorithm to always find such graphs. however, the Handshaking Lemma can be useful for showing that some graphs can't exist. (if the sum of the degrees of each vertex is an odd number... what can we conclude?)
    Thankyou for your reply

    The thing i was thinking about handshaking lemma though - we don't know how many nodes there are (i could have misread something though, forgive me)

    There could be 5 vertices (each connected to each other). Like a star.

    Or with a bipartite graph, there could be k(4, 4)...which would mean there would be 8 vertices?

    Neither planar.

    But there could be more i'm not thinking of, and one possibly being planar...

    EDIT: I think im thinking of a different hand shaking lemma, and not the one specific for planar graph. Going to have a read through that one .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32
    Oh! I didn't see the word 'planar'. That changes the question completely. You're right, neither K5 or K4,4 can be planar (Kuratowski's Theorem). I'm sorry I can't help more.

    I wonder if you could use brute force and show that these are the only two graphs which every vertex having degree 4 on the plane. If you do so, then you have shown there is no connected simple planar graph with that condition.

    EDIT: i was thinking what you were thinking for the Handshaking Lemma. my mistake.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by AshleyCS View Post
    Is there a connected planar (simple) graph such that:
    (a) each vertex has degree 4?
    Planar graphs. Hint please :)-untitled.gif
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2010
    Posts
    13
    Quote Originally Posted by Plato View Post
    Click image for larger version. 

Name:	untitled.GIF 
Views:	41 
Size:	1.9 KB 
ID:	19748
    How did you manage to come up with that!?

    Apart from you blatently being a genious

    Was there a particular method you used? Or just messed around with the vertices?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by AshleyCS View Post
    How did you manage to come up with that!?
    Was there a particular method you used? Or just messed around with the vertices?
    Forty years of experience.
    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
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 25th 2010, 10:18 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