- #1

- 334

- 44

- Homework Statement:
- The length of a longest path in a certain connected graph G is 6. Show that if G contains two paths P and P' of length 6, then P and P' must have at least one vertex in common.

- Relevant Equations:
- G is connected means that for any vertices u and v in G, there exists a u-v path in G.

Let ##P = (u_1, u_2, \dots, u_7)## and ##P' = (v_1, v_2, \dots, v_7)##. If there were a vertex ##w## such that ##w## is adjacent to ##u_1## and for all ##i##, ##u_i \neq w##, then we'd have a path of length 8 ##(w, u_1, u_2, \dots, u_7)##. So no such ##w## exists in ##G##. By definition of connected, there exists a ##v_1 - u_1## path. And so it must be of the form ##(v_1, \dots, u_j, u_1)## for some ##u_i##. But i'm not sure how/if this relates to ##P## and ##P'## sharing a common vertex.

Also I don't think ##P## or ##P'## can be a loop otherwise we could find a path of length greater than 6.

Also I don't think ##P## or ##P'## can be a loop otherwise we could find a path of length greater than 6.