edited by
12,481 views
27 votes
27 votes

A graph is planar if and only if,

  1. It does not contain a subgraph homeomorphic to $k_{5}$ and $k_{3, 3}$.
  2. It does not contain a subgraph isomorphic to $k_{5}$ and $k_{3, 3}$.
  3. It does not contain a subgraph isomorphic to $k_{5}$ or $k_{3, 3}$
  4. It does not contain a subgraph homeomorphic to $k_{5}$ or $k_{3, 3}$.
edited by

2 Answers

Best answer
26 votes
26 votes

A graph is non planar if and only if it contains a sub graph which is homeomorphic to $K_5$ or $K_{3,3}$. 

This is KURATOWSKI theorem.

Homeomorphism is different from homomorphism which in turn is different from isomorphism.

  • If an isomorphism exists between two graphs, then the graphs are called isomorphic. An isomorphism exists between two graphs $G$ and $H$ if there exists a bijection between the vertex sets of $G$ and $H$ such that any two vertices $u$ and $v$ of $G$ are adjacent in G if and only if their corresponding mapped vertices in $H,$ $f(u)$ and $ f(v)$ are adjacent.

  • Graph homomorphism is a mapping between two graphs that respects their structure. Two graphs $G$ and $H$ are homomorphic if there exists a function from V(G) to V(H) that maps endpoints of each edge in G to endpoints of an edge in H.

  • If a homomorphism $f : G → H$ is a bijection (a one-to-one correspondence between vertices of G and H) whose inverse function is also a graph homomorphism exists, then $G$ and $H$ are isomorphic.

  • Two graphs $G$ and $H$ are homeomorphic if there is a graph isomorphism from some subdivision of $G$ to some subdivision of $H.$

  • Hence every isomorphic graphs are also homeomorphic but not vice versa.

Hence (D) is the answer.

https://math.stackexchange.com/questions/183133/difference-between-graph-homomorphism-and-graph-isomorphism

selected by
5 votes
5 votes
D is the correct answer becoz ,

 

as we know that k5 is non -planner graph , it is prroved by corollary1 :  if graph is planner with v veritices and e edges where v>=3, must have  e<=3v-63v-6

as we know that k3-3 is non -planner graph , it is prroved by corollary 2:  if graph is planner with v veritices and e edges where v>=3, must have  e<=2v-4

now homemorphic and isoporphic both are different , so graph homeoporphic to any one of k5 or k3-3 then such graph is non-planner , but graph isomorphic to k5 and k3,3 is also non planner
edited by
Answer:

Related questions

29 votes
29 votes
6 answers
1
makhdoom ghaya asked Nov 22, 2016
9,214 views
Indicate which of the following well-formed formulae are valid:$\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)...
20 votes
20 votes
3 answers
2
makhdoom ghaya asked Nov 22, 2016
9,032 views
Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:$R_{1} \cap R_{2}$ is not regular.$R_{1} \cup R_{2}$ is regular.$\Sigma^{*}-R_{1}$ is regu...
46 votes
46 votes
2 answers
3
makhdoom ghaya asked Nov 22, 2016
12,508 views
It is undecidable whether:An arbitrary Turing machine halts after $100$ steps.A Turing machine prints a specific letter.A Turing machine computes the products of two numb...
27 votes
27 votes
2 answers
4
makhdoom ghaya asked Nov 22, 2016
16,680 views
Recursive languages are:A proper superset of context free languages.Always recognizable by pushdown automata.Also called type $0$ languages.Recognizable by Turing machine...