in Graph Theory edited by
373 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.$
in Graph Theory edited by
373 views

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true