# Cycles in undirected graph: reducing to minimum

I am working on the problem of finding cycles in an undirected graph. I made up my solution by first detecting if any cycles are present with a DFS algorithms and detecting any backtracking, and second, recursively explore all the found backtracked edges until I find the starting vertex. The problem I have is that this approach gives additional cycles, and I don't know how I can remove them in a post-processing step.

The classical way is to represent the cycles as binary vectors, and then XOR them by pairs: if the result is equal to another cycle, then the latter can be removed.

For example, consider the following graph, that obviously has only two basic cycles:

Exploring all possible cycles will give these 3:

c1: 1-2-3
c2: 2-3-4
c3: 1-2-4-3


Converting to binary vectors:

edge | c1   c2   c3
1-2  | 1    0    1
1-3  | 1    0    1
1-4  | 0    0    0
2-3  | 1    1    0
2-4  | 0    1    1
3-4  | 0    1    1


Computing $$c1 \oplus c2$$ will give 110011, which is equal to c3, so we can remove c3.

But in many situations, this is not enough. For example, consider the following graph, having $$v=4$$ vertices and $$e=6$$ edges.

A well know result states that for a single-connected graph with $$v$$ vertices and $$e$$ edges, the number of cycles will be $$c=e-v+1$$, so we have 6-4+1=3 cycles in this example.

But by proceeding with my approach, I get the following 4 cycles:

c1:   1-2-3
c2:   1-2-4
c3:   1-3-4
c4:   2-3-4


If I convert them to binary vectors and XOR them, I am not able to remove the additional cycle.

edge | c1  c2  c3  c4
1-2  | 1   1   0   0
1-3  | 1   0   1   0
1-4  | 0   1   1   0
2-3  | 1   0   0   1
2-4  | 0   1   0   1
3-4  | 0   0   1   1

• $$c1 \oplus c2 = 011110$$
• $$c1 \oplus c3 = 101101$$
• $$c1 \oplus c4 = 110011$$
• $$c2 \oplus c3 = 110011$$
• $$c2 \oplus c4 = 101101$$
• $$c3 \oplus c4 = 011110$$

All these computations produce binary vectors with 4 '1', while all the initial cycles have 3. Thus I can remove none.

Note that this not only a matter of a (single) one additional cycle. For more complex graph (say, Petersen graph for example), I get more than one additional cycles.

I am looking for any ideas on how to remove the additional cycles.

Edit: As suggested in answer, I have build the incidence matrices for the two examples above:

             A1                A2
vert:      1 2 3 4           1 2 3 4
1 | 1 1 0 0 |     1 | 1 1 0 0 |
2 | 0 1 1 0 |     2 | 0 1 1 0 |
edges: 3 | 1 0 1 0 |     3 | 1 0 1 0 |
4 | 0 1 0 1 |     4 | 0 1 0 1 |
5 | 0 0 1 1 |     5 | 0 0 1 1 |
6 | 1 0 0 1 |


Edit 2 For A2, I computed the Reduced Echelon Form (that I understand is useful to find the solutions to $$AX=0$$):

$$A2 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$$

But this stills end up with a null vector...

Edit 3: I come back to this question as I still didn't get it. The answer from @Yuval Filmus suggest to solve $$A x = 0$$ to find the cycle basis. But what exactly represents the different $$x_i$$ values? Because if I make a parallel with linear algebra, then using the matrix $$A2$$, this would mean I need to solve this:

\begin{aligned} x_1 + x_2 &= 0 \\ x_2 + x_3 &= 0 \\ x_1 + x_3 &= 0 \\ x_2 + x_4 &= 0 \\ x_3 + x_4 &= 0 \\ x_1 + x_4 &= 0 \\ \end{aligned}

Beside the fact that the solution to this is $$\{0,0,0,0\}$$, I don't understant what $$x_i$$ represents.

• Additional detail: I don't want to rebuild graph theory ;-) I am just looking for a way to make my implementation work, and I have the feeling that I missed something. – kebs Dec 7 '17 at 9:17
• For the record: this codingthematrix.com/slides/Gaussian_Elimination.pdf has some good explanation of Gaussian Elimitation for binary matrices (p.31) – kebs Mar 5 at 11:41

Consider the incidence matrix of your graph, which is the $E \times V$ matrix in which each row contains exactly two 1s, corresponding to the vertices constituting the given edge, and the rest of the entries are 0. We think of the entries as belonging to $\mathbb{Z}_2$. A set of edges is in the left kernel of the matrix iff it is an XOR of cycles; it is known as the cycle space of your graph. You can find a basis for the cycle basis by finding a basis for the left kernel (this is an exercise in linear algebra). The basis will contain $|E|-|V|+c$ elements, where $c$ is the number of connected components.
If you don't like XOR, you can instead orient your edges arbitrarily, and then use the orientation to form a matrix in which each row contains one $1$ entry and one $-1$ entry. The left kernel of the matrix over the integers is known as the integral cycle space (also described in the link above), and it consists of sums (with integer coefficients) of cycles, where now a cycle is a sum of edges, some of which are possibly negated so that the orientations match.
• I'm ok with building the matrix (see edit) but I don't understand next step. If I try to find $x$ for $x^T A = 0^T$, I get a null vector... What did I miss ? – kebs Dec 9 '17 at 10:11