1. We consider trying to draw Qk graphs on surfaces. A. Show that Q3 can be...

Transcribed Image Text:

1. We consider trying to draw Qk graphs on surfaces. A. Show that Q3 can be drawn on the plane without edges crossing. The quickest way is to actually draw it. B. Use the fact that Q4 has no triangles as subgraphs and an edge counting argument similar to that used for K3,3 to show that Q4 cannot be drawn on the plane without edges crossing. Some data to recall: Q4 has n = 16 vertices and m = 32 edges. What would r have to be in Euler's equation? C. The graph Q4 is isomorphic to C4 X C4. Use this fact to draw Q4 on the torus, using the representation in Figure 1. Figure 1. A representation of the one-holed torus. D. Recall that the graph Q5 has n = 32 vertices and m = 80 edges. Since Q5 is bipartite, there are no triangles as subgraphs. Use a total edge count argument to show that r ≤ 40. If you feed this information into Euler's equation n- m + r= 2 - 2h for the h-holed torus, find a lower bound on h. 1. We consider trying to draw Qk graphs on surfaces. A. Show that Q3 can be drawn on the plane without edges crossing. The quickest way is to actually draw it. B. Use the fact that Q4 has no triangles as subgraphs and an edge counting argument similar to that used for K3,3 to show that Q4 cannot be drawn on the plane without edges crossing. Some data to recall: Q4 has n = 16 vertices and m = 32 edges. What would r have to be in Euler's equation? C. The graph Q4 is isomorphic to C4 X C4. Use this fact to draw Q4 on the torus, using the representation in Figure 1. Figure 1. A representation of the one-holed torus. D. Recall that the graph Q5 has n = 32 vertices and m = 80 edges. Since Q5 is bipartite, there are no triangles as subgraphs. Use a total edge count argument to show that r ≤ 40. If you feed this information into Euler's equation n- m + r= 2 - 2h for the h-holed torus, find a lower bound on h.

Answer rating: 100% (QA)

A To draw Q3 on the plane without edges crossing start with a square and connect each pair of opposi... View the full answer