Prove K3,3 is not planar.

Question

Question

Prove K_3,3 is not planar.

Answer 1

Answer #1

Using Euler's Formula ( n + e -f = 2), and

Further for a planar graph, e<= 2n - 4

e in k3,3 = 3*3

= 9

n = 6

but 9 <= 2*6 - 4 is false

So, k3,3 is not planar

Answer 2

Similar Homework Help Questions

For each of the following graphs draw a planar representation or show that it has a...

For each of the following graphs draw a planar representation or show that it has a subgraph homeomorphic to K5 or K3,3: For each of the following graphs draw a planar representation or show that it has a subgraph homeomorphic to K; or K3,3: (a) (b) (c) (d)
8. Determine whether each graph is planar. If the graph is planar, redraw it so that...

8. Determine whether each graph is planar. If the graph is planar, redraw it so that no edges cross; otherwise, find a subgraph homeomorphic to either K5 or K3,3 (a) (10 pts) See Figure in 3. (b) (5 pts) See Figure in 4 Figure 3: Graph for Question 8(a) مل a e С Figure 4: Graph for Question 8(b)
Problem B: Show that the following graph is non planar by showing the K3,3 configuration it...

Problem B: Show that the following graph is non planar by showing the K3,3 configuration it contains.

3. For each of the following graphs, determine if the graph is planar. If it is,...

3. For each of the following graphs, determine if the graph is planar. If it is, draw a plane representation of the graph; if not, indicate a subgraph homeomorphic to Kor K3,3 G
3. Which of the following graphs are planar? Find K 3.3 or Ks configurations in the...

3. Which of the following graphs are planar? Find K 3.3 or Ks configurations in the nonplanar graphs (almost all are K3,3). (k) (1)
Graph theory For which values of k is the A -cube Q_1 planar? For which values...

Graph theory For which values of k is the A -cube Q_1 planar? For which values of r, s and t is the complete tripartite graph K_r,s,t planar? Use Kuratowski's Theorem to prove that the camwood graph below is non-planar. What is the genus of the Heawood Graph?

Are the following graphs planar? If so, show a planar representation and if not, explain why not. ь. Are the following graphs planar? If so, show a planar representation and if not, explain why...

Are the following graphs planar? If so, show a planar representation and if not, explain why not. ь. Are the following graphs planar? If so, show a planar representation and if not, explain why not. ь.
r. Give a planar embedding of the graph 2. Determine whether the given graph is planar. Give a planar embedding of the...

r. Give a planar embedding of the graph 2. Determine whether the given graph is planar. Give a planar embedding of the graph or provide an argument that none exis ts. r. Give a planar embedding of the graph 2. Determine whether the given graph is planar. Give a planar embedding of the graph or provide an argument that none exis ts.
Please do NOT apply Kuratowski's theorem. Because of the symmetry between edges in each graph, it...

Please do NOT apply Kuratowski's theorem. Because of the symmetry between edges in each graph, it suffices to find a plane embedding for each graph removing an edge (draw an example). Problem 4. (5 points each.) 1. Show that when any edge is removed from K3,3, the resulting subgraph is planar. 2. Show that when any edge is removed from K5, the resulting subgraph is planar.

(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use...

(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use this fact to prove the six-color theorem: for any planar graph there exists a coloring with six colors, i.e. an assignment of six given colors (e.g. red, orange, yellow, green, blue, purple) to the vertices such that any two vertices connected by an edge have different colors. (Hint: use induction, and in the inductive step remove some verter and all edges...