# Why do people use “K” to represent a complete graph?

Why do people use the letter "K", rather than "C", to represent a complete graph? Does it come from German "komplett"?

-
Either that, or the person who named it wrote in English but couldn't spell. –  Gerry Myerson May 23 '13 at 13:15
... but in german the complete graph is usually called "vollständiger Graph" ... without any K ... –  martini May 23 '13 at 13:15
Because $C_n$ already denotes cycle graphs? –  Martin May 23 '13 at 13:16
@martini I know nothing about German and google translation tells me that which possibly be wrong. –  J.A.F May 23 '13 at 13:17
@Martin That's an possible explanation. In my opinion, they are fundamental concepts in graph theory hence it is not that easy to tell which one comes first. –  J.A.F May 23 '13 at 13:21

My understanding is that Harary introduced the notation $K_5$ and $K_{3,3}$ for the graphs appearing in Kuratowski's theorem, and the choice of $K$ as symbol was in honour of Kuratowski.

I must admit that I do not have this first hand, but it was certainly the accepted explanation as I was "growing up" graph theoretically.

Edit: The story is in print on page 259 of Doug West's "Introduction to Graph Theory".

-
I only have the second edition of the book which doesn't seem to contain anything of relevance on page 259. Do you mean the passage Kasimir Kuratowski once asked Frank Harary about the origin of the notation for $K_5$ and $K_{3,3}$. Harary replied, "The $K$ in $K_5$ stands for Kasimir, and the $K$ in $K_{3,3}$ stands for Kuratowski!" (p. 246 of the second edition)? –  Martin May 25 '13 at 14:26
@Martin: I'll check the edition next time I'm in my office. –  Chris Godsil May 25 '13 at 18:50
The complete graph on $n$ vertices is denoted by $K_n$. Some sources claim that the letter K in this notation stands for the German word komplett, but the German name for a complete graph, vollständiger Graph, does not contain the letter K, and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory.