# 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. Oct 20 '16 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 Oct 21 '16 at 11:34
• en.wikipedia.org/wiki/Longest_path_problem – adrianN Oct 21 '16 at 14:02