3 +example

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.

2 edited tags
1

# Is this statement about the real edge space of a graph known or trivial?

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.