I am struggling to understand the concept of isomorphism. By definition, if G and H are two simple graphs so that V(g) and V(h) are the number of nodes in G and H respectively, then isomorphism is defined as a function from f:V(G)->V(H) with the following properties: (i) f being bot surjective and injective (thus, f is a bijection) (ii) the nodes u and v are neighbours/adjacent in G iff the nodes f(u) and f(v) are adjacent in H.

Now, for the problem.

Draw a complete graph with five nodes. For this, I understand that a complete graph has each vertex adjacent to all other vertices in the graph. (See the illustration).

enter image description here

Then, is it possible to find another (non-isomorphic!) complete graph with five nodes? How do I approach this question?

Intuitively, I think that it is not possible, since a complete graph implies that every pair of distinct vertices ought to be connected by a unique edge, and thus, all possibilities are exhausted. However, this is not based on any written work. How can I approach the question?

  • $\begingroup$ There's a reason why one speaks of "the" complete graph with five nodes. $\endgroup$ – Hagen von Eitzen Dec 7 '13 at 14:01
  • $\begingroup$ And this implies that THE complete graph is the only possibility? $\endgroup$ – aprilrocks92 Dec 7 '13 at 14:04

Assume $G,H$ are complete graphs, both with $n$ nodes. Then both $V(G)$ and $V(H)$ are sets of $n$ elements, i.e. of the same cardinality. Thus let $f\colon V(G)\to V(H)$ be any bijection between these sets. One immediately verifies that $f$ is a graph isomorphism: Indeed, $u,v$ are adjacent in $G$ iff $u\ne v$ iff $f(u)\ne f(v)$ iff $f(u),f(v)$ are adjacent in $H$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.