Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - please help~graph theory problem 2

  1. #1
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12

    please help~graph theory problem 2

    Let H be the graph with vertex set Z14 and with edge set
    E(H) = {{x, x + 1} : x 2 Z14} [ {{x, x + 5} : x 2 {0, 2, 4, 6, 8, 10, 12}}.
    (a) Find the length of a shortest cycle in H and use this to prove that H is non-planar.
    (b) Give a different (from part (a)) proof that H is non-planar.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2008
    Posts
    18

    Swap

    If you give me an answer to question 1 of assignment 4 I will give you the answer to this question. I do not know what to do in question one I am totlaly lost anything you know about it would help so much!!! If you give me an answer I will give you the answer to question 2 :-)))
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12
    yeh, i do know how to do part of question 1, do u still need it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2008
    Posts
    18

    :-)

    Of course. Tell me what you know and if it helps then I will give you the answer to your question. I have done both of 2 and 3, they both took a while so I will not give you them for nothing of course. Best regards :-)))
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    6
    I worked out the answer yesterday if the guy above didn't already give it to you.

    Any luck with question 1?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12
    i have actually done Q2 & Q3, and half of Q1
    but not quite sure about how to prove the graph in Q2 is a subdivision of K3,3
    can anyone help?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12
    by the way, did u guys get 6 as the shortest cycle length for Q2?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Sep 2008
    Posts
    18
    6 is the shortest cycle. I think question 1 is harder then 2. If you can do 1 then you can definetly do 2. How have you approached 1?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2008
    Posts
    4
    Quote Originally Posted by ycdfd View Post
    but not quite sure about how to prove the graph in Q2 is a subdivision of K3,3
    can anyone help?
    I've drawn a diagram of a subgraph that is a subdivision of K3,3:

    The red vertices are the result of subdivisions, so they can be ignored. (there is also an edge from 7 to 8, but I forgot to draw it in)

    What I want to know is, is this the answer to 2.a. or 2.b?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Sep 2008
    Posts
    18
    2b. How did you appoach 1.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2008
    Posts
    4
    I have no idea how to approach one. Did anyone go to the tutorial today?

    How do I use the 6-cycle to prove H is non-planar?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Sep 2008
    Posts
    18
    your graph is exactly what I did.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Sep 2008
    Posts
    18
    We should work on 1. The tutor said to me question 1 is worth more then q. 2 because it is harder. No one knew how to do it at the tute.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Oct 2008
    Posts
    6
    2a's got to do with Euler's Formula and the fact that:

    2q = r*(no. edges in each region) > r*(length of shortest cycle)
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Oct 2008
    Posts
    4
    Thanks Tom.

    I think I've found the key to question 1. It's damn hard to explain, but I'll try.

    In order for a 9-regular graph to satisfy the property that any subgraph with more than p/2 - 1 edges has a vertex of degree at least 2, you need to have separate groups of nodes whose only link to each other is through the vertices of H, where H's vertices are not in any of those groups, but form bridges between groups. And in order for these groups to connect to H, they need to have odd numbers of elements, and furthermore, since the graph is 9-regular, only k elements from each group can connect to H, where k is odd and less than 9. Therefore, since the vertices of H are also 9-regular, for each vertex in H, there needs to be at least three groups of vertices connecting to each other through it. So, if if the vertices of H and all the edges incident with the vertices of H are removed from G, then what remains is a graph with at least 3*|V (H)| components of odd order, where these components are the separate groups of vertices that were previously bridged by H.

    So, to complete the proof, all I need to do is rewrite the above paragraph with justifications for all of my leaps of logic.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 19th 2011, 03:29 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 09:36 PM
  3. graph theory problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 20th 2009, 08:50 PM
  4. graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 25th 2009, 08:07 AM
  5. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 01:50 PM

Search Tags


/mathhelpforum @mathhelpforum