# Isomorphism of Complete Graphs

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).

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?

• There's a reason why one speaks of "the" complete graph with five nodes. – Hagen von Eitzen Dec 7 '13 at 14:01
• And this implies that THE complete graph is the only possibility? – 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$.