8
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ Either that, or the person who named it wrote in English but couldn't spell. $\endgroup$ May 23, 2013 at 13:15
  • 3
    $\begingroup$ ... but in german the complete graph is usually called "vollständiger Graph" ... without any K ... $\endgroup$
    – martini
    May 23, 2013 at 13:15
  • 4
    $\begingroup$ Because $C_n$ already denotes cycle graphs? $\endgroup$
    – Martin
    May 23, 2013 at 13:16
  • $\begingroup$ @martini I know nothing about German and google translation tells me that which possibly be wrong. $\endgroup$ May 23, 2013 at 13:17
  • $\begingroup$ @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. $\endgroup$ May 23, 2013 at 13:21

2 Answers 2

7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Martin
    May 25, 2013 at 14:26
  • $\begingroup$ @Martin: I'll check the edition next time I'm in my office. $\endgroup$ May 25, 2013 at 18:50
4
$\begingroup$

A search in Wikipedia gives:

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.

$\endgroup$
5
  • $\begingroup$ Thanks! Kazimierz Kuratowski was born in 1896. I cannot believe this fundamental concept was defined later than 1896. $\endgroup$ May 23, 2013 at 13:28
  • 1
    $\begingroup$ Joe, other than Euler & those bridges, there wasn't much graph theory around until the 1930s. $\endgroup$ May 23, 2013 at 13:30
  • $\begingroup$ I thought it was for Kuratowski also, but I don't know why I thought that! $\endgroup$
    – MJD
    May 23, 2013 at 13:45
  • $\begingroup$ @Joe: We're not discussing the origin of the concept, just the origin of the standard notation. But Gerry's comment is accurate too. $\endgroup$ May 25, 2013 at 18:53
  • $\begingroup$ @ChrisGodsil I got your point. I assumed the origin of the standard notation and the origin of the concept were at the same time, which is not correct. $\endgroup$ May 26, 2013 at 14:20

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.