I just started learning some basic graph theory stuff and I was wondering if the following claim/proof is valid and whether it has any implications.

I want to show that the Maximum Path of any graph must be one of the M-alternating paths formed by the maximum matching.

My reasoning for this is that if there exists a maximum matching in a graph, then that graph does not have any M-augmenting paths, therefore, the longest path in such a graph would have to be M-alternating.

Is this correct? Does this have any consequences? Any small pointers are helpful!! Thank you!


It's not necessary.

Consider this graph on 6 vertices, $\{0, 1, 2, 3, 4, 5\}$, and the following edges: $(0, 1)$, $(2, 3)$, $(4, 5)$ - which form the maximum matching - and also $(1, 3)$ and $(3, 5)$.

enter image description here

Then your maximal (acyclic) path is $0-1-3-5-4$, which is not an alternating path.

  • $\begingroup$ Ah I see, thank you! $\endgroup$
    – molocule
    Dec 1 '18 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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