UGC NET CSE | December 2013 | Part 2 | Question: 39

Question

A graph is non-planar if and only if it contains a subgraph homomorphic to

• A. $K_{3,2} \text{ or } K_5$
• B. $K_{3,3} \text{ or } K_6$
• C. $K_{3,3} \text{ or } K_5$
• D. $K_{2,3} \text{ or } K_5$

Answer 1

According to Kuratowski's theorem a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or of K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).

Hence,Option(C)K_3,3 or K_5.

_Reference:-https://en.wikipedia.org/wiki/Kuratowski%27s_theorem

Answer 2

if any graph G contains a subdivision of K₅ and K_3,3 as a subgraph, then G must be non-planar.

Every non-planar graph contains K₅ or K_3,3 as a subgraph.

Reffrence :http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

Answer 3

Answer C

A planar graph  can be drawn in a plane without graph edges crossing.
•    Complete graphs are planar only for n<=4
•    All bipartite graphs are planar except K 3,3
•    Planar graph divides plane into faces F = |E| – |V| +2
•    Degree (face) is the number of nodes along its boundary.
•    In a planar graph, |E| <= 3(|V|-2)
•    Any non planar graph contains subgraphs homomorphic to K5 or K3,3.  

Answer 4

k3,3 and K5 is not planner so any graph which contains k3,3 and K5 as a subgraph is not planner.