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)$.
Then your maximal (acyclic) path is $0-1-3-5-4$, which is not an alternating path.