Talk:Biconnected graph

Biconnected graph

"In other words, a biconnected graph is nonseparable, meaning if any edge were to be removed, the graph will remain connected." I changed "edge" to "vertex" because the original description doesn't hold in a graph with 2 vertices (which is, by definition, a biconnected graph). Kmote (talk) 20:18, 13 February 2008 (UTC)

Definition of an undirected biconnected graph

"A biconnected undirected graph G is a set of vertices V so that every vertex has at least two connecting edges (an adjacency list of at least size two), connecting to separate vertices other than itself."

Take the graph G(V, E), V = { A, B, C, D, E }, E = { AC, AE, BE, CE, DE, BD } doesn't 'every vertex have at least two connecting edges connecting to separate vertices other than itself"? And yet doesn't it also have an articulation vertex at E? Sahuagin (talk) 01:26, 8 December 2007 (UTC)

I agree. I removed that line. —David Eppstein (talk) 01:47, 8 December 2007 (UTC)

Definition of biconnected strongly connected directed graph

"A biconnected strongly connected directed graph G is a set of vertices V so that every vertex has at least two in-degree vertices, and at least two out-degree vertices; ie. there are at least two independent paths from any vertex to any other vertex."

Take the following graph: {AB, AC, BA, BC, CA, CB, DE, DF, ED, EF, FE, FD, AD, DA}. Every vertex has in-degree and out-degree at least 2. However, every path from A to F must go through AD, so there aren't two independent paths from A to F. In fact, removing AD leaves a graph which is not strongly connected. This seems to imply that the condition given is necessary but not sufficient. -Pablo —Preceding unsigned comment added by 190.139.45.183 (talk) 13:02, 21 March 2009 (UTC)

Yes, the definition was nonsense. The adjective "biconnected" is not used much for digraphs, but I inserted one existing definition. McKay (talk) 22:16, 21 March 2009 (UTC)