







CTK Exchange
mr_homm
Member since May2205

Aug1205, 07:44 AM (EST) 

"K_3,3 graph"

I was just looking at the bipartite graph page, and I noticed a different way to see that K_3,3 is nonplanar. (No doubt there are many ways to see this.) If the edges AE and WC are connected with straight lines instead of the curves in the figure, you can visualize the graph as a Moebius strip in 3d. Rectangle WABG is a section of the strip, BGEC is the next section along the strip, and ECWA is a third section connecting the first two and completing the strip. Where edges WC and AE cross, we are seeing the half twist in the section ECWA, looking at the strip edge on. Once you see the graph this way, it is obvious how to draw it on a Moebius strip. Just draw three lines across the width of the strip and a line around the edge. The points of intersection are the vertices of K_3,3 and the line segments connecting them are the edges. But if K3,3 were planar, it would have a natural orientation inherited from the plane, hence could not be filled with a nonorientable surface. (If K_3,3 were imbedded in the plane, the path around the Moebius strip would now appear to follow a patchwork of orientable areas, and so would not reverse orientation.) Therefore K_3,3 is nonplanar. I think this is interesting, because the other two dimensional embedding mentioned (in a torus) can't be used so directly to prove K_3,3 is nonplanar, because the torus is orientable. Perhaps other topological properties of the torus could be used instead, but none is as obviously incompatible with a plane embedding as nonorientability. The same trick works for K_5 as well: Taking the vertices 4 at a time you can see trapezoidal strips that you can think of as segments of a Moebius strip. Follow each strip to the edge and imagine that the paper folds under and conects to the next trapezoid. After going around 5 times, you have of course a Moebius strip because you've made an odd number of folds. To draw this graph on a Moebius strip, place 5 equally spaced points along its edge and connect them across the strip with a zigzag line. This way of folding a Moebius strip is very closely related to the cuttheknot logo, omitting the extra knots at the corners. Isn't it interesting that the cuttheknot logo can be used to prove K_5 is nonplanar? Stuart Anderson 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



mr_homm
Member since May2205

Aug1505, 12:00 PM (EST) 

2. "RE: K_3,3 graph"
In response to message #1

>>Isn't it interesting that the cuttheknot logo can be used >>to prove K_5 is nonplanar? > >Feeling myself on the cutting edge. > >Thank you. You're welcome. I thought the connection to the logo very amusing. I have made myself paper models of these graphs drawn on Moebius strips, just to see if my drawing instructions worked correctly. They do. The graphs are surprisingly unclutteredlooking with no selfintersections. To my eye at least, K_3,3 appears as just 3 rectangles conneced end to end, and K_5 as 5 isoceles triangles connected on alternate sides. Thank you for attaching my comments to your 3 utilities page. I am glad you liked them. Stuart Anderson 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



Inquirer
guest

Dec2208, 08:10 AM (EST) 

3. "RE: K_3,3 graph"
In response to message #0

Hello, I have a question about the proof on the bipartite graph page. Why is it true that for any bipartite graph, "no two nodes are connected by 2 edges" (as the proof requires)? I probably do not fully grasp what a bipartite graph is, but from the definitions I find on the web, nothing seems to prevent a vertex in the one set and a vertex in the other to be connected by 2 rather than 1 edge. Perhpas you don't call that a graph but a 'pseudograph'? But as I understand 'pseudographs' are a subset of all 'graphs'... To be sure for the 3 utilities problem it makes no sense to have 2 edges between two vertices. However in the proof a general statement about bipartite graphs is made. Thank you! 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 19962018 Alexander Bogomolny

