Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Oct 9th 2008, 10:27 PM
ycdfd
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.
• Oct 21st 2008, 06:44 PM
gloiterbox
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 :-)))
• Oct 21st 2008, 08:54 PM
ycdfd
yeh, i do know how to do part of question 1, do u still need it?
• Oct 21st 2008, 10:44 PM
gloiterbox
:-)
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 :-)))
• Oct 22nd 2008, 02:29 AM
TomP
I worked out the answer yesterday if the guy above didn't already give it to you.

Any luck with question 1?
• Oct 22nd 2008, 03:17 AM
ycdfd
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?
• Oct 22nd 2008, 03:20 AM
ycdfd
by the way, did u guys get 6 as the shortest cycle length for Q2?
• Oct 22nd 2008, 03:33 AM
gloiterbox
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?
• Oct 22nd 2008, 03:49 AM
MarkW
Quote:

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:
http://img136.imageshack.us/img136/6504/k33fr0.png
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?
• Oct 22nd 2008, 03:54 AM
gloiterbox
2b. How did you appoach 1.
• Oct 22nd 2008, 03:56 AM
MarkW
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?
• Oct 22nd 2008, 03:56 AM
gloiterbox
your graph is exactly what I did.
• Oct 22nd 2008, 03:59 AM
gloiterbox
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.
• Oct 22nd 2008, 02:58 PM
TomP
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)
• Oct 22nd 2008, 09:28 PM
MarkW
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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last