# In a DAG, longest path where every vertex has degree at most 2

I have a directed acyclic graph (DAG). How I can find the longest path using only vertices with degree at most 2?

Currently, I try this

def all_simple_paths(g):
for path in all_paths(g):
if len(path) > 2:
center_path = path[1:-1]
nodes_degree = g.degree(center_path).values()
if max(nodes_degree) <= 2:
return path


but that might output any path, rather than the longest path.

• Welcome to CS.SE! I'm having a hard time understanding what you are asking. What does "the more longest paths" mean? Are you looking for the longest path, such that every vertex in the path has degree 2? Please edit your question to clarify. Also, please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. (For instance, it's not clear what all_paths() is, or path[1:-1].) Thank you!
– D.W.
Commented Oct 20, 2016 at 18:28
• A path where every vertex has degree 2 is a cycle. So you are looking for the longest cycle in a directed acyclic graph (DAG)? I assume you want to compute the longest path in a DAG.
– dtt
Commented Oct 21, 2016 at 11:34
• en.wikipedia.org/wiki/Longest_path_problem Commented Oct 21, 2016 at 14:02