1
$\begingroup$

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!

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

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}$.

$\endgroup$

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.