– Background Information:
I am studying graph theory in discrete mathematics. As I was practicing questions I came across this solution, provided by my professor. I think her method can be simplified, but I need someone to confirm it, thanks.
– Question and Solution:
– My approach:
Let's use proof by contradiction, so suppose P1 and P2 don't have a common vertex.
Then we know that P1 and P2 are disconnected, so they are two different components. This means the graph G, is disconnected into two components G1 and G2 for paths P1 and P2 respectively.
We know the question says the graph is connected, but we have shown that the graph is disconnected when there is no common vertex. Thus, this is a contradiction, and there must be at least one common node between P1 and P2 to keep the graph connected.
Summary: We can see that we don't need to get into the shortest path P3 and proving paths P1 and P2 are not maximum paths because of path longest path p4 (my professor solution).
– My question:
Is my strategy simplified? Does it solve the problem? Let me know what you think.
Best Answer
If two paths are disjoint then it doesn't mean that they are into two different components of $G$. It's indeed true, but if you assume that the statement you want to prove is true. So in fact you're just forming a cyclic "proof", which isn't a valid one.
To see that the proof that the two paths are disjoint is not so easy, try to disprove the fact that there isn't a path between any vertex from $P_1$ and any vertex from $P_2$.