Which of the following Graph is/are planer? Choose the most appropriate answer from the options given below:
A and B only
A graph is planar if it can be redrawn in the plane with no edges crossing. By Kuratowski's theorem a graph is non-planar exactly when it contains a subdivision of K5 or K3,3; for a connected planar simple graph, e ≤ 3v − 6.
Step 1 — Graph A has 6 vertices and 8 edges: the cycle a–b–d–e–f–c–a plus the chords b–f and c–d. The two chords cross only because both are drawn inside the cycle; drawing c–d outside the cycle removes the crossing, so A is planar.
Step 2 — Graph B has 6 vertices and 10 edges: a–c, a–d, a–e, a–f, b–c, b–d, b–f, c–e, d–f, e–f. Without a–f it is the triangular prism with triangles a–c–e and b–d–f joined by a–d, c–b, e–f, which is planar; a–f is a diagonal of the quadrilateral face a–e–f–d, so it can be added without a crossing. B is planar.
Step 3 — Graph C has 9 vertices and 15 edges. Take the parts {a, e, f} and {b, d, g}: a–b, a–d, a–g, e–b, e–d, f–b, f–g are edges, e reaches g through the path e–h–g and f reaches d through f–c–d. This is a subdivision of K3,3, so by Kuratowski's theorem C is not planar.
So the planar graphs are A and B. Any choice that includes C is wrong, and the choices naming only A or only B each leave out one planar graph.
A and B only option is correct.
If $K_n$ is complete simple graph of n vertices and $K_{m,n}$ is complete bipartite graph then arrange the following non-planner graph in ascending order on the bases of the minimum number of crossings.
A. $K_6$
B. $K_7$
C. $K_{4,4}$
D. $K_{5,5}$
Choose the correct answer from the options given below: