This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Seems to be redundant, given the Connectivity (graph theory) article. Radagast3 ( talk) 00:17, 1 May 2008 (UTC)
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)
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)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
Seems to be redundant, given the Connectivity (graph theory) article. Radagast3 ( talk) 00:17, 1 May 2008 (UTC)
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)
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)