This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

This should NOT redirect from "k-connected graph". The two are very distinct concepts, and the latter NEEDS an entry...

You're right. Fixed. —David Eppstein 16:49, 22 October 2006 (UTC)Reply

This seems to be redundant, given the Connectivity (graph theory) article. Radagast3 (talk) 00:18, 1 May 2008 (UTC)Reply

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

Agreed, but I'm too busy to do it. ;) Radagast3 (talk) 00:36, 1 May 2008 (UTC)Reply

This article has previously been nominated to be moved. Please review prior discussions if you are considering renomination. Discussions Not moved, 24 July 2025, to undefined, see discussion. Moved, 20 September 2025, from undefined to undefined, see discussion.

Gabow's paper states ${\displaystyle O(km\ln(n^{2}/m))}$ complexity, not ${\displaystyle O(n^{3})}$. Reminiscenza (talk) 11:40, 2 June 2015 (UTC)Reply

There's no contradiction between those two bounds. k is necessarily O(n) and m is necessarily O(n²). So if you eliminate those two variables and express everything in terms of n, you get O(n³).—David Eppstein (talk) 15:20, 2 June 2015 (UTC)Reply

Yes, but why we need to express everything in terms of n? For graph algorithms, complexity is usually expressed in terms of m and n, and whatever other parameters available - so that the bound is useful for both sparse and dense graphs. Bound ${\displaystyle O(n^{3})}$ is at least misleading for sparse graphs, where it is possible that ${\displaystyle k=O(1)}$, ${\displaystyle m=O(n\ln n)}$ and overall complexity would be ${\displaystyle O(n\ln ^{2}n)}$, much better than ${\displaystyle O(n^{3})}$. — Preceding unsigned comment added by Reminiscenza (talk • contribs) 06:21, 3 June 2015 (UTC)Reply

• In graph theory, a graph ${\displaystyle G}$ with edge set ${\displaystyle E(G)}$ is said to be ${\displaystyle k}$-edge-connected if ${\displaystyle G\setminus X}$ is connected for all ${\displaystyle X\subseteq E(G)}$ with ${\displaystyle \left|X\right|<k}$.
  • Is it syntactically correct to say ${\displaystyle G\setminus X}$, as G is a graph (= a set of vertices and a set of edges connecting some vertices) whereas X is a set of edges? --Abdull (talk) 15:33, 27 July 2008 (UTC)Reply

• If a graph ${\displaystyle G}$ is ${\displaystyle k}$-edge-connected then ${\displaystyle k\leq \delta (G)}$, where ${\displaystyle \delta (G)}$ is the minimum degree of any vertex ${\displaystyle v\in V(G)}$.
  • Can we make this theorem stronger by saying ${\displaystyle k<\delta (G)}$, as we could delete all but one edges from a vertex and still have all vertices of this connected graph connected? --Abdull (talk) 15:55, 27 July 2008 (UTC)Reply

It is usual, even on this WIKI, to write a graph as an ordered pair (V,E) with vertex set V and edge set E. This article does it the other way around. Is there a compelling reason for this? Leen Droogendijk (talk) 11:31, 28 June 2012 (UTC)Reply

Consider a graph G of a single vertex and no edge. According to the formal definition, G is k-edge-connected for all k. On the other hand, the minimum vertex degree of G is 0, thus the statement of the second section does not hold for this example. --Jalpar75 —Preceding undated comment added 15:59, 9 August 2013 (UTC)Reply

There is a move discussion in progress on Talk:K-vertex-connected graph which affects this page. Please participate on that page and not in this talk page section. Thank you. —RMCD bot 17:04, 24 July 2025 (UTC)Reply

There is a move discussion in progress on Talk:K-vertex-connected graph which affects this page. Please participate on that page and not in this talk page section. Thank you. —RMCD bot 11:49, 20 September 2025 (UTC)Reply