edited by
395 views
2 votes
2 votes

Which of the following statements about simple graphs are true ?

  1. Two complete graphs on $m,n$ vertices respectively, are isomorphic to each other if and only if $m=n.$
  2. Wheel graph on $n$ vertices, $n \geq 4,$ is never a planar graph.
  3. Bipartite graph is always planar graph.
  4. Complement of a cycle graph on $n$ vertices is connected if and only if $n \geq 5.$
edited by

1 Answer

2 votes
2 votes

A is true.
Any two complete graphs $\text{K}_{n}$ and $\text{K}_{m}$ are isomorphic if any only if $n = m.$ If $n$ is not equal to $m,$ then it is clear that we cannot have a $1-1$ matching between the vertices of the two graphs, because there will be more vertices in one graph than in the other. If $n = m$ then any matching will work, since all pairs of distinct vertices are connected by an edge in both graphs. Notice that in the graphs below, any matching of the vertices will ensure the isomorphism definition is satisfied.



B is false as Wn is always planar. C is false as $\text{K}
(3,3)$ is not planar. D is true.
Complement of a cycle graph on $n$ vertices is connected if and only if $n \geq 5.$


edited by
Answer:

Related questions