Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Either that, or the person who named it wrote in English but couldn't spell. –  Gerry Myerson May 23 '13 at 13:15
3  
... but in german the complete graph is usually called "vollständiger Graph" ... without any K ... –  martini May 23 '13 at 13:15
4  
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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

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.

share|improve this answer
    
Thanks! Kazimierz Kuratowski was born in 1896. I cannot believe this fundamental concept was defined later than 1896. –  J.A.F May 23 '13 at 13:28
1  
Joe, other than Euler & those bridges, there wasn't much graph theory around until the 1930s. –  Gerry Myerson May 23 '13 at 13:30
    
I thought it was for Kuratowski also, but I don't know why I thought that! –  MJD May 23 '13 at 13:45
    
@Joe: We're not discussing the origin of the concept, just the origin of the standard notation. But Gerry's comment is accurate too. –  Chris Godsil May 25 '13 at 18:53
    
@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. –  J.A.F May 26 '13 at 14:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.