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.

2. ## 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 :-)))

3. yeh, i do know how to do part of question 1, do u still need it?

4. ## :-)

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 :-)))

5. I worked out the answer yesterday if the guy above didn't already give it to you.

Any luck with question 1?

6. 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?

7. by the way, did u guys get 6 as the shortest cycle length for Q2?

8. 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?

9. Originally Posted by ycdfd
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?

10. 2b. How did you appoach 1.

11. 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?

12. your graph is exactly what I did.

13. 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.

14. 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)

15. 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.

Page 1 of 2 12 Last