Prove that for any 2 edges $e_1$, $e_2$ of a connected graph $G$ there exists a path having $e_1$ as its first edge and $e_2$ as its last edge.

Prove that for any 2 edges $$e_1$$, $$e_2$$ of a connected graph $$G$$ there exists a path having $$e_1$$ as its first edge and $$e_2$$ as its last edge.

Attempt

Let $$e_1=u_1v_1$$ and $$e_2=u_2v_2$$ in $$A(G)$$. Since $$G$$ is connected, there exists a $$v_1u_2-$$path. This path can contain either $$u_1$$ or $$v_2$$, if it contains both vertices we are done. Suppose it contains $$u_1$$, since $$v_2$$ is adjacent to $$v_1$$ this produces a $$v_1v_2-$$path. Analogous the other case.

If it contains neither, since $$u_1$$ is adjacent to $$v_1$$ and $$v_2$$ is adjacent to $$u_2$$, this produces a $$u_1v_2-$$trajectory that has $$e_1$$ as its first edge and $$e_2$$ as its last edge.

Is it ok?

• "if it contains both vertices we are done" how come? Apr 30 '21 at 2:31

If $$e_1,e_2$$ are adjacent then $$e_1e_2$$ is a path satisfying the conditions. Otherwise, let $$u,v$$ and $$x,y$$ be $$e_1$$'s and $$e_2$$'s endpoints respectively and consider $$G-e_1-e_2$$; it has at most three connected components, so at least one $$C$$ containing two of $$u,v,x,y$$.
If $$C$$ contains only $$u,v$$ or only $$x,y$$ among the four special vertices, adding $$e_1$$ and $$e_2$$ back will not connect $$C$$ to the rest of the graph, so $$G$$ is disconnected – contradiction. Hence $$C$$ contains a path $$p$$ from one vertex incident to $$e_1$$ to one vertex incident to $$e_2$$; $$e_1pe_2$$ is then a path satisfying the conditions.
• Is $C$ one of the components of $G-e_1-e_2$? I don't quite understand the part that says "so at least one $C$ containing two of $u ,v, x, y$". Can you explain it, please? Apr 30 '21 at 4:38
• @Gabriela We are applying the pigeonhole principle here; $C$ is indeed a component of $G-e_1-e_2$. Apr 30 '21 at 4:39