Question

Consider the following graphs. Select the graphs that are planar. There are 3 correct answers out of 5.

A. The wheel graph, W6.

B. The complete bipartite graph, K3,3.

C. The 4-cube graph, Q4.

D. The complete graph, K4.

E. The cycle graph, C5.

Answer 1

Planar Graphs :

A graph is said to be embedded in a plane or planar if it can be drawn in the plane so that its edges intersect only at the vertices.

Thus if we draw a graph such that the edges intersect only at the vertices then such graph is called a planar graph.

Examples:

Here G is a planar graph but H is not a planar graph.

A) The wheel graph W₆

For W₆ graph the edges intersect only at the vertices hence W₆ is a planar graph.

B) The Complete bipartite graph K_3,3

Here the edge with color orange is intersecting another edge. Thus K_3,3 is not a planar graph.

C) The 4-cube graph Q₄

Here the edge is intersecting another edge. Thus Q₄ is not a planar graph.

D) The complete graph K₄

Here edges intersect only at the vertices hence K₄ is a planar graph.

E) The cycle graph C₅

Here edges intersect only at the vertices hence C₅ is a planar graph.

B) One more way to prove K_3,3 is not a planar graph.

Proof:

Suppose K_3,3 is a planar graph.

As K_3,3 has no cycle of length < 4

It implies every face of G must have degree at least 4.

If graph G(p,q) is Planar graph with faces f then it satisfies Euler's formula

i.e. p-q+f = 2

By Euler's Formula for K_3,3

which is a contradiction.

Hence our assumption is wrong.

Thus K_3,3 is not a planar graph.

C) One more way to prove Q₄ is not a planar graph.

Proof:

Following is the one more drawing of Q₄ graph.

Q₄ graph contains K_3,3 graph which is with red vertices and black edges.

and as K_3,3, is not a planar graph hence Q₄ can not be a planar graph.