Talk:K-vertex-connected graph

Seems to be redundant, given the Connectivity (graph theory) article. Radagast3 (talk) 00:17, 1 May 2008 (UTC)

There is plenty of material to expand this and K-edge-connected graph into two separate long articles. —David Eppstein (talk) 00:20, 1 May 2008 (UTC)

And that would be a good solution. At present they are redundandant, and the Connectivity (graph theory) article is needed as a place for theorems relating the two kinds of conectivity. Radagast3 (talk) 00:35, 1 May 2008 (UTC)

Definition and complete graphs

Does there have to be a special case to say that a complete graph with k+1 nodes is k-vertex-connected? It seems that the first definition on the page would make the complete graph infinity-vertex-connected (if an empty graph is considered connected), but the second definition (in terms of disjoint paths) would make it k-vertex-connected. 130.63.92.179 (talk) 20:40, 25 November 2008 (UTC)

Good point - it seems a bit odd to say a k-complete graph is j-connected for all j in N. I've slightly modified the definition to say that it applies only when k ≤ |V(G)|, which ought to be sufficient. I think most references I've seen just overlook this minor point. Dcoetzee 23:03, 25 November 2008 (UTC)

I think the new version makes K_n n-connected. Usually it is only regarded as (n-1)-connected. I think the reason is that anomalies occur if the connectivity exceeds the minimum degree. The path-connectivity approach gives n-1 too. I think the only non-tricky definition is to make an explicit exception. McKay (talk) 04:58, 8 March 2009 (UTC)

In Schrijver's book, complete graphs K_n are explicitly stated to be infinity-connected (p. 237). According to Wolfram MathWorld, they are n-connected. However, the most usual definition in graph theory is that K_n (n-1)-connected... Apparently, the experts are not able to get their act together! I think it is necessary to mention the inconsistent definitions for complete graphs. Ratfox (talk) 16:40, 3 December 2010 (UTC)

Definition is broken (incorrect) as of Jan 15 2013

I just added a note to the definition of the first paragraph to correct it where it breaks. This should be considered a band-aid, and the primary definition requires careful rewriting to be of a high standard.

It becomes evident the definition is not consistent when considering the tetrahedral graph. This graph is 3-connected (via Steinitz' theorem, among others) and to verify this the definition and its alternative phrasing force you to consider whether a single vertex is connected or not. Applying the two phrasings of the definition to this question gives two different answers, making the second variant of the phrasing a logically distinct definition from the first. The second phrasing says it is disconnected (which is against convention), but which is necessary for the tetrahedron to be considered 3-connected (by either phrasing).

So I believe this definition (i.e. both phrasings of the definition) needs to be carefully re-written to take care of these edge effect cases. Maybe one of you classy folk can plagiarize a high-standard textbook if no-one can be bothered finding the right words to simply and correctly define the concept. It's too much effort for me. /toen — Preceding unsigned comment added by 49.176.98.63 (talk) 12:15, 15 January 2013 (UTC)

A single vertex is certainly connected. I don't think there can be any debate over that question. But the graph of the tetrahedron is a complete graph, which is usually considered as a special case in the definition. According to this special case the tetrahedron is 3-conneced but not 4-connected. You would recover the same connectivity if you used a formulation according to which the graph with zero vertices is not connected (it has the wrong number of connected components, zero, whereas a connected graph has one connected component) but probably it's less confusing to leave that out. —David Eppstein (talk) 16:31, 15 January 2013 (UTC)

However, the initial definition doesn't say that complete graphs are excluded and also doesn't say that disconnecting the graph must be possible. It only says that if deleting sets of fewer than k vertices gives a connected graph, then G is k-connected. This implies that K₄ is 4-connected, with no need to consider empty graphs. (What is unclear so far is whether K₄ is 5-connected.) Then we say that complete graphs are a special case because they can't be disconnected, but until then nobody mentioned anything about disconnection being required.

A second problem is that it says "remains connected" when it might not have been connected to start with.

We should also not assume that beginners realise that "fewer than k" includes 0.

I will put in the definition used in Diestel's book (4th edn) since it works for all graphs including complete graphs. McKay (talk) 04:07, 16 January 2013 (UTC)