# How to find a cycle with a property in a graph

Let's have a graph with this edge list:

edgelist =
{s -> 1, s -> 2, 1 -> 3, 2 -> 1, 2 -> 4, 3 -> 2, 3 -> t, 4 -> 3, 4 -> t};


I want to know how to find all cycles with length>3 that must contain s or t or both

• Use any of the answers here to find cycles, and then select only the cycles that satisfy your conditions. Jul 26, 2015 at 13:38
• I tried to do it like this, and i get the same cycle twice at the end. it's a cycle that starts with s and contains t and the other starts with t and contains s. It's the same, and i don't want this. Jul 26, 2015 at 13:51
• Welcome to Mathematica.SE! I suggest the following: 0) Browse the common pitfalls question 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! Jul 26, 2015 at 17:14

If those edges are directed, then you haven't got any cycles involving s or t. To specify undirected edges use \[UndirectedEdge], which shows up on SE as <->.

edgeList = {s <-> 1, s <-> 2, 1 <-> 3, 2 <-> 1, 2 <-> 4, 3 <-> 2, 3 <-> t, 4 <-> 3, 4 <-> t};
G = Graph[edgeList, VertexLabels -> "Name"];

tCycle = FindCycle[{G, t}, {4, Infinity}, All];
sCycle = FindCycle[{G, s}, {4, Infinity}, All];
Union[tCycle, sCycle]


Update

Nasi points out that the union contains the same edge list twice. Sorting each at levels 1 and 2 before taking the union will get rid of the duplicates.

tCycle = Map[Sort, tCycle, 2]
sCycle = Map[Sort, sCycle, 2]
Union[tCycle, sCycle]


Perhaps there is a clever SameTest option for Union that allows more flexibility.

• I know this method, but if we use this first we get a cycle that contains both s and t and then we get another cycle that contains both and the union shows them both with a different starting vertex Aug 2, 2015 at 10:32