MathCastle
Graph TheoryMediumGraph Algorithms

Graph Algorithms · Medium problem

A graph has vertices k,l,m,n,o,p,qk,l,m,n,o,p,q and edges kl,km,ln,mn,mo,np,op,pq,oqkl, km, ln, mn, mo, np, op, pq, oq. Running a DFS from kk that visits each vertex's unvisited neighbors in alphabetical order discovers a back edge connecting nn and pp. What is the length (number of edges) of the cycle that this back edge forms with the DFS tree path between nn and pp?