# Show that $K_n \boxtimes K_n = K_{n^2}$, where $K_n$ is a complete graph of $n$th order.

Show that $K_n \boxtimes K_n = K_{n^2}$. I thought that I could show that the number of vertices are the same, i.e.

$$|V(K_{n^2})| = |V(K_n \boxtimes K_n)|$$

and since it is a complete graph, it should follow that they are exactly the same set of vertices.

But what about the edges? I could consider that there is a pair of vertices $(g,h)$ such that they are not connected, and follow a redcutio ad absurdum fashion? Or even induction? In any case, I do not know how to get it started. Any help would be great!

• Note that $K_n$ has $\binom{n}{2}$ edges.. – onimoni Mar 12 '14 at 9:03
• Or equivalently $\frac{n(n-1)}{2}$.. – onimoni Mar 12 '14 at 9:11

You need to show that any two vertices of $K_n \boxtimes K_n$ are adjacent. Let $(a,b), (g,h) \in K_n \boxtimes K_n$. If $a=g$, since $b$ and $h$ are adjacent, we have $(a,b)$ and $(g,h)$ are adjacent. If $a\neq g$ and $b\neq h$, since $a$ and $g$ are adjacent, also $b$ and $h$ are adjacent, we have $(a,b)$ and $(g,h)$ are adjacent. Thus $K_n \boxtimes K_n$ is a complete graph with $n^2$ vertices and it must be $K_{n^2}$.