# Given a Spanning Tree and an Edge Not on the Spanning Tree, How to Form a Cycle Base?

I have a graph with Edge E and Vertex V, I can find the spanning tree using Kruskal algorithm, now I want to find all the cycle bases that are created by utilitizing that spanning tree and the edges that are not on the tree, any algorithm that allows me to do that, besides brute force search?

I can, of course, starts from one vertex of the non-spanning tree edge, gets all the edges, explore all of them, retracts if I find dead end, until I come back to the other vertex of the edge. But this is a bit, err... brutal. Any other ideas?

• You don't need Kruskal, Ngu! You can find a spanning tree trivially -- it doesn't have to be minimum. Newcomers, see mathoverflow.net/questions/1443/… for Ngu's initial question. – TonyK Oct 22 '09 at 18:15
• Sure, I can find spanning tree-- with or without Kruskal. But my question is how to form the cycle base without resorting to something what I call 'brute force'. – Graviton Oct 23 '09 at 1:34

You are interested in a basis of the cycle space of $G$. Orient $G$ in any way. Let $\partial(G)$ be the edge-vertex incidence matrix of $G$. A basis of the cycle space is given by a basis for $\ker \partial(G)$. To get the answer to your question note that if you take any spanning tree $T$ and you consider the edges of $E-T$, there will be a unique element of the cycle space that is $1$ on a given edge of $E-T$ and $0$ on the others. Finding such an element for each edge of $E-T$ will yield a new basis for $\ker \partial(G)$.