The question "does there exist a simple path in a given graph with at least k edges" is NP-complete.
Die Frage "Gibt es in einem gegebenen Graphen einen Pfad mit mindestens k Kanten" ist NP-vollständig.