Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
It's certainly not if and only if, because for instance a graph that is itself a cycle of length greater than three has the spanning property (there is only one cycle, it is a u-cycle for every u, and it spans the cycle space) but is not 3-connected. –  David Eppstein Sep 28 '11 at 6:34
    
The u-cycles do span the cycle space (for either interpretation of the term (see below)) but they do not span R^E, as the statement claims they should not. –  Erik Aas Sep 29 '11 at 4:08
add comment

3 Answers

up vote 3 down vote accepted

(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$.

share|improve this answer
    
I think that the question was about the $u$-cycles. This one seems eaisier. However, I liked your previous example on $K_4 \cdot K_4$ that the cycles may generate the edge space even if the graph is not 3-connected. (Which unfortunately disappeared.) Perhaps, the condition has to be modified a bit. There is still some hope with a little bit modified condition, since if G contains 1-vertex cut or 2-vertex cut not containing $u$, then the cycles cannot generate the edge space. –  Martin Tancer Sep 30 '11 at 6:38
    
Oops, I misread it. But what I proved is a good start, see Theorem B which I just added. The comment after it, which includes $K_4\cdot K_4$, shows that only one direction is possible. –  Brendan McKay Sep 30 '11 at 8:41
    
Nice! I don't know if this means the answer to the original question is "yes", but I'll accept it as an answer anyway. –  Erik Aas Oct 1 '11 at 3:21
add comment

I think the statement is false. It certainly fails for $K_3$ for example.

It also fails for $K_{3,3}$. Let the vertices in one part be 1,2,3 for example and 4,5,6 in the other.

Then consider the cycles containing 14. There are 4 of length 4: 1425, 1426, 1435, 1436 and 4 of length 6: 142536, 142636, 143526, 143625.

Since there are 9 edges in the graph, the 8 cycles containing 14 cannot span the 9 dimensional edge space.

share|improve this answer
    
I think that $K_3$ is not a counterexample: it is not 3-connected; and it is not possible to get the characteristic vector of a single edge in $K_3$. Regarding the second answer, why don't you count cycles containing 15 and 16? –  Martin Tancer Sep 28 '11 at 8:04
    
Why isn't $K_3$ 3-connected? I do count 15 and 16: these are cycles so the last vertex is connected to the first. –  Anthony Quas Sep 28 '11 at 11:48
    
I would say that the standard definition of $k$-connected graph requires that the number of vertices is at least $k+1$. It is important convention because of Menger's theorems. I have checked that wikipedia does not agree with me, thus this might be a matter of "culture" (and discusses special cases of complete graphs). In any case, I guess that the question was asked with this assumption. Regarding the second part of the anwser: You are still missing cycles like 1526 (assuming that 1 is the vertex $u$ in the question). Actually, $K_{3,3}$ is surely not a counterexample: First it is easy to –  Martin Tancer Sep 28 '11 at 13:19
    
span an edge containing $u$. With simplified notation: $2\cdot 14 = 1425 + 1436 - 152436$. Next, it is also possible to span an edge not containing 1: $1425 + 153426 - 143526 = 2\cdot 15 + 2\cdot 24$, then $2\cdot 15$ can be subtracted, since it is an edge containing 1. –  Martin Tancer Sep 28 '11 at 13:23
    
Sorry. I thought that we were talking about all cycles containing a specified edge; not a vertex. –  Anthony Quas Sep 28 '11 at 17:13
add comment

The set of $u$-cycles of a graph $G$ spans $\mathbb{R}^{E(G)}$ if and only if $G$ consists has only the single vertex $u$. For otherwise, the space spanned by the cycles in the graph is a vector space of dimension $E(G)-V(G)+1 < E(G)$.

In an attempt to make your question less trivial, I assumed that what you really meant is to characterize the pairs $(G,u)$ for which the set of $u$-cycles spans the whole cycle space of $G$. But in this case the answer is different than what you ask: the correct characterization is that $u$ should belong to every biconnected component of $G$.

One direction is easy: if $u$ does not belong to some biconnected component $C$, then every $u$-cycle has at most one vertex in $C$ (the articulation point connecting the component containing $u$ to $C$) and no edges in $C$, so it is not possible to represent any of the cycles in $C$ as combinations of $u$-cycles.

In the other direction, we need to find a cycle basis of $u$-cycles, which we may do separately in each biconnected component, so assume without loss of generality that $G$ is biconnected. Then $G$ has an open ear decomposition, a partition of its edges into a sequence of subgraphs, where the first subgraph is a cycle containing $u$ and the subsequent ones are paths, and where the two endpoints of each path belong to earlier subgraphs in the sequence while all the other vertices in each path do not belong to any earlier subgraph. It is not hard to show by induction on the number of subgraphs that, for each subgraph in the sequence, the two endpoints have disjoint paths to $u$ in the union of the earlier subgraphs. So the sequence of cycles $C_0$, $C_1$, etc where $C_0$ is the first subgraph in the ear decomposition and where for $i>0$ $C_i$ is the $i$th subgraph in the ear decomposition together with the two paths from its endpoints to $u$ forms a set of $u$-cycles. Each cycle in this sequence is independent of the earlier ones because it includes at least one edge not appearing in earlier ones, and the total number of cycles matches the dimension of the cycle space, so it forms a cycle basis of $u$-cycles as desired.

share|improve this answer
    
I don't agree with your claim that the space spanned by the cycles has dimension E-V+1. This is true for the cycle space over Z_2, but not for the 'real cycle space' (if defined as the subspace of R^E spanned by characteristic vectors of cycles - Wikipedia defines the cycle space only for Z and Z_2), I believe - I will edit my question to contain an example. The statement you prove above is not what I was thinking of but is nonetheless very nice! (continued) –  Erik Aas Sep 29 '11 at 4:04
    
So, I was indeed thinking of spanning the 'real cycle space' but more importantly show that it coincides with the edge space, and that it is spanned by the subset of cycles given by the u-cycles. –  Erik Aas Sep 29 '11 at 4:05
1  
I don't think this is about real vs $Z_2$, but more about dropping signs that are irrelevant for $Z_2$ but should not have been dropped in other characteristics. To define a real cycle space I would assign an (arbitrary) orientation to each edge, and then define the characteristic vector of an (oriented) cycle to have $+1$ in the coordinate for an edge when the orientation of the cycle is consistent with that of the edge, and $-1$ when it's inconsistent. I'm pretty sure that if you do it that way you still get the same dimension, $E-V+1$, as in the $Z_2$ case. –  David Eppstein Sep 29 '11 at 5:59
    
Good point - that definition of 'real (cycle/edge) space' would probably make more sense in general. In my question I'm thinking of the edges as undirected so the characteristic vectors mentioned there are really those of sets of undirected edges (which happen to form cycles). So the vectors of a cycle and its reverse would be the same, for example. The undirected model is also natural if one is thinking about quantities that add up along edges independently of direction (like lengths). –  Erik Aas Sep 29 '11 at 6:44
    
I took the characteristic vectors of the 4 3-cycles and 3 4-cycles in $K_4$ and the rank over the reals is 6. In fact 4 times each edge is the sum of the cycles containing it minus the sum of the cycles not containing it. So this is an example where the cycles span the full real edge space. I bet a similar simple proof holds for complete graphs, and I think only a few cycle lengths will be needed. –  Brendan McKay Sep 29 '11 at 8:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.