Talk:Complete graph

POV on "worst case"

In the current version, the sentence "(..) a complete graph can be the worst case for large connected systems like social and computer networks" is POV. It needs explanation. Otherwise the statement is not generally true and needs to be removed. Why should a complete social network be any bad? Worse in comparison to what?

I guess the person who wrote it was thinking of benefit-cost-ratio. But that needs some elaboration and possibly sources to make it credible. Otherwise not worthy of an existence in an encyclopedia. Tang Wenlong (talk) 21:27, 28 April 2008 (UTC)

Er, although this statement is poorly-written, I think this just means that it's the worst-case size (as in worst-case analysis) for such a network; which is of course not expressing a point of view. Dcoetzee 21:30, 28 April 2008 (UTC)

Enneagon and Decagon

This article has pictures of all regular polygons from a triangle to an octagon. The triangle has nothing but its sides and corners, but the octagon looks very complicated. Can anyone see how complicated an enneagon or decagon will look?? 66.245.86.215 01:21, 16 Oct 2004 (UTC)

You mean K₉ and K₁₀? As a general rule, the complete graph on n vertices, K_n, has n × (n - 1) / 2 edges; so K₉ has 9 × (9 - 1) / 2 = 36 edges, and K₁₀ has 10 × (10 - 1) / 2 = 45. So yeah, they can look quite complicated!  :-) I guess since we've already got K₁ to K₈, we might as well add 9 and 10; or we could add K₁₀₀ just to illustrate how messy they can get... --Ejrh 02:22, 18 Oct 2004 (UTC)

I added up to $K_{11}$. I'm too lazy to create higher ones (pity as we need them for simplex Petrie polygons...) Professor M. Fiendish, Esq. 11:12, 9 September 2009 (UTC)

K100

K100 added! It's really beautiful. Alpt 18:41, 30 October 2006 (UTC)

yes, it is, but it adds little to the article. More like "ooh, look what my computer can do". I suppose it might illustrate that the number of connections increases rapidly —Preceding unsigned comment added by 24.18.43.240 (talk • contribs)

It's completely inappropriate and I'm going to remove it. Even at the highest resolution it is hard to see the edges but only the interference pattern they make. It will only confuse people who come to this page for information on complete graphs. --McKay 01:56, 30 December 2006 (UTC)

I agree, thanks. I was going to remove it myself, and I am glad you did it first. -- Dominus 03:37, 30 December 2006 (UTC)

Extending this wiki to include complete digraphs

Silly point - but this wiki could also define the concept for directional graphs. This request is motivated by the next two entries.

Is there a general way of determining all of the subgraphs of K_j UP TO isomorphism?

Yes, this is a simple exercise, and I will probably hunt it down on the internet. But, say, for K₄ how many subgraphs are there (where I would like to differentiate between subgraphs that are NOT isomophic to one another - clearly it is simple to enumerate all the subgraphs, calculate their adjacency matrices and get a computer program to get rid of all of the similar matrices so that you are left with ONLY isomorphically distinct subgraphs - but, surely, this has been done already?).

ConcernedScientist 19:01, 30 May 2007 (UTC)

Is there a general way of determining all of the directed subgraphs of a directed K_j UP TO isomorphism?

Same as above request, but everything is to do with directed graphs (so their should be more subgraphs up to isomorphism...). ConcernedScientist 19:01, 30 May 2007 (UTC)

3D complete graph?

I have yet to see one but I think it would be very interesting. -Eeky 06:56, 6 August 2007 (UTC)

The simplex family has vertex/edge sets as complete graphs, so the tetrahedron is 3D, and pentachoron is 4D. Tom Ruen 14:15, 6 August 2007 (UTC)

Interesting. So shouldn't simplex mention complete graphs as being 3D equivalents? -Eeky 15:41, 6 August 2007 (UTC)

Any graph, no matter how many vertices, can be embedded without crossings in 3d, for instance by placing the ith vertex at the coordinates (i,i², i³). —David Eppstein 15:13, 6 August 2007 (UTC)

OK, but is there a 12-vertex version? -Eeky 15:41, 6 August 2007 (UTC)

Yes, but I was too lazy to make a graphic. Professor M. Fiendish, Esq. 11:13, 9 September 2009 (UTC)

Full mesh

As I understand, the term "complete graph" means the same as "full mesh" in computer science (especially networking). Does anyone object to mentioning this fact in this article? --chrylis (talk) 05:04, 3 September 2008 (UTC)

Origin of the K in Kn

Every German source I have seen says that the K is in honour of Kuratowski. "Complete graph" is "vollständiger Graph" in German, not "kompletter Graph".

Pluslucis (talk) 15:17, 1 March 2010 (UTC)

K4 example makes it look non-planar.

In Planar graph, it states "The complete graph K4 is planar" and links to this article. Then, here, we have a drawing of K4 which makes it look non-planar (i.e. two of the edges cross in the drawing). This is bound to be confusing to people. I think it would make sense to either use the drawing of K4 from Planar graph, or at least have a note on the drawing here pointing out that there is an alternate way to draw the graph which makes its planarity more apparent. -- RoySmith (talk) 17:58, 1 May 2012 (UTC)

French Wikipedia has a separate article for "Tetrahedral graph"; that could be the way to go... AnonMoos (talk) 15:23, 12 November 2012 (UTC)

Alternative formula for the number of edges in a complete graph

Not sure if there is any reason to mention it in the article or to add it to the infobox, but $\textstyle {\frac {n(n-1)}{2}}={n \choose 2}$ (where ${n \choose 2}$ is a binomial coefficient), and the latter is more succinct. 77.126.47.196 (talk) 12:52, 3 February 2018 (UTC)

It's similar to a formula for triangular numbers: ${n+1 \choose 2}$. 77.126.47.196 (talk) 09:40, 5 February 2018 (UTC)

And of course, you can also find the number through summation, though that may actually be more verbose: $\sum _{i=1}^{n}(i-1)$. 77.126.47.196 (talk) 10:04, 5 February 2018 (UTC)

Is this correct?

The section Properties contains this sentence:

"They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices."

(Where the word "they" refers to complete graphs.)

But if n ≥ 3, for the complete graph K_n, removing any two vertices disconnects the graph.

(Because they are the endpoints of some edge.)

Or am I misunderstanding something? 2601:200:C000:1A0:87C:FF45:2757:A6C9 (talk) 17:36, 3 January 2022 (UTC)

No, it doesn't. If you remove two vertices from $K_{n}$ you are left with $K_{n-2}$, which is still connected. In this context, removing a vertex means also removing all edges incident to that vertex. —David Eppstein (talk) 17:41, 3 January 2022 (UTC)

For the record

The following example of a complete digraph was posted:

I Ching as complete digraph on bagua

The eight bagua or trigrams form the verticies of a directed graph given by hexagrams in the I Ching. The hexagrams are ordered pairs of trigrams with the lower considered first, the upper second. Since there is a hexagram for every pair of bagua, in both orders, there is a directed edge in each direction for each pair of trigrams. Eight loops are included in the directed graph since there is a hexagram for each doubled trigram. The 56 edges and 8 loops are labeled 1 to 64 in a lookup table, but the sequence is obscure. In the case of a pair of trigrams corresponding to Greek elements (Earth ☷, Water ☵, Air ☰, and Fire ☲.), the oppositely directed edges are consecutive.<ref b:I Ching/Octal Bagua /ref>

Reverted! Complete digraph mentioned in lede. Very old topic. Supports article well. Rgdboer (talk) 04:20, 17 February 2022 (UTC) Provide WB link Rgdboer (talk) 04:34, 17 February 2022 (UTC)

So you're trying to use content you yourself wrote on another open Wiki (Wikibooks) as a reference for content here? It is very obviously not a reliable source, even setting aside the questions of relevance (why a complete digraph + loops between trigrams rather than a complete bipartite graph between lower and upper sets of trigrams, or a complete system of combinations of elements rather than a graph, or a Boolean algebra, or...) and of whether there is sufficient significance to either topic. —David Eppstein (talk) 06:32, 17 February 2022 (UTC)

Complete digraphs

@David Eppstein I appreciate you adding the citation, but I don't understand why you had to attack me in the edit summary: "supply requested notation for basic and obvious notation for which User:Dr. Universe could easily have run a search instead of making busywork for other editors". Couldn't you have just added the citation and not complained about how "basic and obvious" it was and not mention me? The reference that you added says that a digraph is "complete" if for every pair vertices (x,y), the edges xy and yx both exist. But the Directed graph article says that "some authors consider a broader definition that allows directed graphs to have such multiple arcs", in which case there could be four edges between (x,y), for example two of them corresponding to xy and two of them corresponding to yx. According to the above definition of "complete" for digraphs, the graph with 4 edges (2 of them being of xy-type and 2 being yx-type) between each pair of vertices (x,y), would also be a complete digraph to those people who allow directed graphs to have such multiple arcs. So in this sense, the definition should be that there's at least one edge going in each direction right? I wasn't sure about this so I wanted to see a reference. Dr. Universe (talk) 01:46, 10 September 2022 (UTC)

Unless otherwise specified, usually only one edge would be allowed in each direction in a digraph. I don't remember ever seeing a definition of complete graphs (without additional qualification in the name) that allowed the edge multiplicities to vary. —David Eppstein (talk) 04:04, 10 September 2022 (UTC)