3,Is the graph K3,4 planar? If yes, give a planar drawing by hand. If not, give a proof of this.
The Correct Answer and Explanation is :
The graph ( K_{3,4} ) is not planar. To understand why, we need to use Kuratowski’s Theorem, which states that a graph is planar if and only if it does not contain a subgraph that is a K5 (complete graph on 5 vertices) or K3,3 (complete bipartite graph on 3 vertices and 3 vertices).
In the case of ( K_{3,4} ), the graph is a complete bipartite graph with 3 vertices on one side and 4 vertices on the other side. The number of edges in ( K_{3,4} ) is 12, as each vertex on the left side is connected to every vertex on the right side.
Proof that ( K_{3,4} ) is non-planar:
- Kuratowski’s Theorem: To prove ( K_{3,4} ) is non-planar, we need to show that it contains a subgraph that is not planar, specifically ( K_{3,3} ), because a subgraph of ( K_{3,4} ) can be found that is isomorphic to ( K_{3,3} ). We can isolate a set of 3 vertices on the left side of ( K_{3,4} ) and 3 vertices on the right side, and these vertices and their edges form a ( K_{3,3} ), which is non-planar.
- ( K_{3,3} ) is Non-Planar: It is known that ( K_{3,3} ) is non-planar because it cannot be drawn on a plane without edges crossing.
Since ( K_{3,4} ) contains a ( K_{3,3} ) subgraph, by Kuratowski’s Theorem, ( K_{3,4} ) is non-planar.
Visualization:
Since ( K_{3,4} ) is non-planar, we can’t give a planar drawing of it. However, I can show a representation of the graph, which illustrates its structure while respecting the fact that it is non-planar.
Let me generate an image to represent the graph structure of ( K_{3,4} ).
Here is the representation of the graph ( K_{3,4} ), showing the two sets of vertices with edges connecting every vertex from the first set to all vertices in the second set. Since ( K_{3,4} ) contains a subgraph that is isomorphic to ( K_{3,3} ), which is non-planar, the graph as a whole is also non-planar.
This visualization highlights the structure, and it shows why such a graph can’t be drawn on a plane without edge crossings, confirming that ( K_{3,4} ) is not planar.