Talk:K-edge-connected graph

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)

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

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)

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

Complexity

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

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)

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 $O(n^{3})$ is at least misleading for sparse graphs, where it is possible that $k=O(1)$, $m=O(n\ln n)$ and overall complexity would be $O(n\ln ^{2}n)$, much better than $O(n^{3})$. — Preceding unsigned comment added by Reminiscenza (talk • contribs) 06:21, 3 June 2015 (UTC)

Proper math

• In graph theory, a graph $G$ with edge set $E(G)$ is said to be $k$-edge-connected if $G\setminus X$ is connected for all $X\subseteq E(G)$ with $\left|X\right|<k$.
  • Is it syntactically correct to say $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)

Stronger

• If a graph $G$ is $k$-edge-connected then $k\leq \delta (G)$, where $\delta (G)$ is the minimum degree of any vertex $v\in V(G)$.
  • Can we make this theorem stronger by saying $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)

Consistency

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)

Contradiction between the formal definition and the next section

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)