2
$\begingroup$

According to me, maximal paths in a graph are those paths which cannot be included in any other larger paths. Could anyone please explain me this with some examples? Also what would happen if the graph happens to contain cycles?

$\endgroup$

1 Answer 1

6
$\begingroup$

We can say a path is maximal if you cannot add any new vertices to it to make it longer. You can contrast this with a path of maximum length: it is the longest path in a graph (so it is also maximal, but note the difference). A bit informally, when something is "maximal", it means you cannot add anything to it to make it larger. When something is "maximum", it is globally the largest "object" there is.

For an example, consider the tree pictured in this Wikipedia article. The path on the vertices $\{1,2,4\}$ is maximal; you cannot add any vertex to it to make it longer. But a maximum path (i.e., longest path) in the tree is on the vertices $\{ 1,4,5,6 \}$. Clearly, it is no problem if the graph you consider contains a cycle. For example, then you can see that not every vertex of the graph can be in a longest path.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.