2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ "if it contains both vertices we are done" how come? $\endgroup$
    – Asinomás
    Apr 30, 2021 at 2:31

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Gabriela
    Apr 30, 2021 at 4:38
  • $\begingroup$ @Gabriela We are applying the pigeonhole principle here; $C$ is indeed a component of $G-e_1-e_2$. $\endgroup$ Apr 30, 2021 at 4:39

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.