The statement is:
($u$ is a fixed node in a fixed graph $G$)


$G$ is 3-connected
if and only if
the set of u-cycles span $\mathbb{R}^{E(G)}$.


A u-cycle is a simple (no vertex repetitions) cycle in G that contains the given node u.


A cycle is identified with its characteristic vector in $\mathbb{R}^{E(G)}$ that is $1$ on the edges in the cycle and $0$ otherwise.


I first thought this would be a standard result on the cycle space of a graph. However, the references I've found have only considered cycle spaces over a field with non-zero characteristic.


EDIT: The 'usual' edge space $\mathbb{Z}\_2^{E(G)}$ is quite different from the 'real' edge space $\mathbb{R}^{E(G)}$. For example the set of (characteristic vectors of) cycles form a m-n+1-dimensional space independently of all other properties of the graph, while the statement above claims the cycle space can indeed be the entire edge space even in non-trivial cases.


Here's an example. Let K\_4 have four nodes 1,2,3,4 and edges indexed so:


1 - {1,2}


2 - {1,3}


3 - {1,4}


4 - {2,3}


5 - {2,4}


6 - {3,4}


The characteristic vectors of the u-cycles (u = '1') 1463, 1562, 3542, 153, 142, 263 (sequences of indices of *edges*) are, row by row:


1 0 1 1 0 1


1 1 0 0 1 1


0 1 1 1 1 0


1 0 1 0 1 0


1 1 0 1 0 0


0 1 1 0 0 1


bluebit.gr (and hopefully any other calculator) tells me this matrix has rank 6, so the cycles given span the entire 6-dimensional real edge space and they are also all u-cycles.



Is this statement about the real edge space of a graph known or trivial?
(RESTART) Here is a complete solution.


Call a graph *3-edge-connected* if the number of components cannot be increased by removing only 1 or 2 edges. (This allows for the graph to be disconnected already.)


Let $R~$ be a ring that has an identity and a left inverse of 2, which I'll call $\frac12$. (For example, a field of characteristic other than 2.)


Given a graph $G~$ with edge-set $E$, let $RE~$ be the module of formal sums $\sum\_{e\in E} c\_e e$, where each $c\_e\in R$, with the usual operations of addition, and multiplication on the left by field elements. Let $RC~$ be the submodule generated by the (edge sets of) cycles.


**Theorem A.** $RE=RC~$ iff $G$ is 3-edge-connected.


**Proof.** If $e$ is an edge cut by itself (i.e., a bridge), it lies on no cycles, so $e\notin RC$. If $e,e'$ is an edge cut of size 2, then any cycle containing $e$ must also contain $e'$, so again $e\notin RC$. Therefore 3-edge-connectivity is necessary.


Conversely, assume $G~$ is 3-edge-connected and choose any $e=(v,w)\in E$. The graph after removing $e$, call it $G-e$, is 2-edge-connected, so by Menger's Theorem there are two edge-disjoint paths $P\_1,P\_2$ in $G-e$ from $v$ to $w$. Now note that
$$ e = \tfrac12((P\_1\cup \{e\}) + (P\_2\cup \{e\}) - (P\_1\cup P\_2)). $$
The three terms on the right are in $RC$, the first two because they are cycles and the third because the union of two edge-disjoint paths with the same endpoints is an edge-disjoint union of cycles. Therefore $e\in RC$.


(ADDITION) Let $u$ be a vertex, and let $C\_u$ be the set of cycles passing through u.


**Theorem B.** If $G~$ is 3-connected, then $RC\_u=RE$.


**Proof.** Let $C~$ be a cycle that does *not* pass through $u$. Since $G~$ is 3-connected, there are 3 paths from $u~$ to $C~$ which are vertex disjoint except at $u$. This divides $C~$ into 3 segments.
Now add the 3 evident cycles through $u~$ that use two segments of $C~$ and subtract the 3 evident cycles through $u~$ that use one segment of $C$. The result is $C$. That is, we can use the cycles through $u~$ to get all the cycles.
Therefore, $RC\_u=RC$, and now apply Theorem A.


If we take two 3-connnected graphs, and glue them together at a single vertex $u$, then also $RC\_u=RE$ for this graph. Yet it isn't 3-connected. So the "if" in Theorem B can't be changed to "iff". We can make an incomplete converse though.


**Theorem C.** If $G~$ is a connected graph and $RC\_u=RE$, then $u$ lies on every 1-cut or 2-cut.


**Proof.** If there is a 1-cut other than $u$, clearly cycles through $u~$ can't reach the edges on the other side of the cut, so $RC\_u\ne RE$. Now suppose there is a 2-cut
$\{x,y\}$ neither of which is $u$. Let $E\_x$ be the edges of $G~$ which are incident to $x~$ but can't be reached from $u~$ except via the 2-cut. Similarly $E\_y$. Every cycle through $u~$ either uses none of $E\_x$ or $E\_y$, or uses exactly one edge from each. Therefore, every vector in $RC\_u$ has the same total coefficient for $E\_x$ as it does for $E\_y$, which is a linear dependence implying $RC\_u\ne RE$.


