How can I check if some specific cycles are in a graph?

How can I check if some specific cycles are in a graph?

myGraph =
Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3,
3 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5,
5 \[UndirectedEdge] 1, 5 \[UndirectedEdge] 6,
6 \[UndirectedEdge] 1, 3 \[UndirectedEdge] 5},
VertexLabels -> "Name"];
myCycles = {{1 \[UndirectedEdge] 6, 6 \[UndirectedEdge] 5,
5 \[UndirectedEdge] 1}, {2 \[UndirectedEdge] 1,
2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4,
4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 1}}


I tried the FindCycle and then check if a given cycle is in the FindCycle. Also is there any simpler method without having to find all cycles in a graph and them check if a cycle is there? This method would work but I wonder if the graph cycle is large then this would be slow.

• If you do FindFundamentalCycles[myGraph] you get the output {{6 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6}, {5 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 5}, {4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4}}. Is this what you were going for or did I misunderstand your question?
– user49048
Commented Feb 19, 2022 at 6:41
• @DiSp0sablE_H3r0 nope, for example I was given a graph myGraph and some cycles myCycles. Now I want to check if cycles in myCycles exist in myGraph or not. For example I have a function like checkCycle[myGraph, myCycles] and I expect the result in this case is {True, True}. The length of myCycles can be one or more.
– hana
Commented Feb 19, 2022 at 6:50

ClearAll[subgraphQ]
subgraphQ[g_] := Apply[And] @* Map[EdgeQ[g, #] &]

subgraphQ[myGraph] /@ myCycles


{True, True}

Also

ClearAll[subgraphQ2]
subgraphQ2[g_] := AllTrue[#, EdgeQ[g, #] &] &

subgraphQ2[myGraph] /@ myCycles

{True, True}

• That is clever. If you want to check two nodes in a graph are connected or not what would you use?
– hana
Commented Feb 19, 2022 at 19:38
• @hana, connectedQ[g_,v1_,v2_]:=MemberQ[AdjacencyList[g,v1], v2]?
– kglr
Commented Feb 20, 2022 at 0:10
• This is simple but not actually work for all cases. Some graphs with two nodes connected but via a long path with many nodes.
– hana
Commented Feb 20, 2022 at 0:18
• oh, just replace AdjacencyList with VertexComponent
– kglr
Commented Feb 20, 2022 at 0:33
• Thanks, that works well.
– hana
Commented Feb 20, 2022 at 0:35