1
$\begingroup$

Given a finite connected graph, let $A$ be a set of edges such that each edge in $A$ is not part of a cycle. Suppose that no path contains all edges in $A$. Must it be true that for some three edges in $A$, no path contains all the three edges?

This is equivalent to showing that if every subset of three edges in $A$ is contained in a path, then there is a path containing all edges in $A$. I’ve tried doing induction, but even going from three to four doesn’t seem obvious. Each set of edges $\{e_1,e_2,e_3\}$ and $\{e_2,e_3,e_4\}$ has a path containing it, but other edges maybe used in both of these paths in various orders.

$\endgroup$
2
  • $\begingroup$ How should I be interpreting the condition "are not part of a cycle"? If, say, it means "there is no cycle in $G$ containing all edges in $A$" then we can always cover all of $A$ by a path unless $A$ is the whole cycle, so I'm wondering if you have something else in mind. $\endgroup$
    – Ben Barber
    Mar 1, 2019 at 17:37
  • $\begingroup$ @BenBarber Sorry, I now realize that my original question wasn't clear. Please see the new version. $\endgroup$
    – user136454
    Mar 1, 2019 at 18:07

1 Answer 1

2
$\begingroup$

Extend $A$ to a spanning tree $T$ of $G$, which is possible greedily for any acyclic subgraph of a connected graph. Since $A$ cannot be covered by a single path, there is a vertex $v$ such that at least $3$ of the branches of $T$ at $v$ lead to components $C_1, C_2, C_3$ containing edges $a_1, a_2, a_3$ of $A$. We claim that these edges cannot be covered by a single path.

Indeed, suppose there were such a path $P$. Fix an orientation of $P$ and label each $a_i$ according to whether $P$ traverses $a_i$ towards or away from $v$. By reversing the orientation and relabelling if necessary we may assume that $P$ traverses $a_1$ and $a_2$ away from $v$. But then there must be a path from $C_1$ to the start point of $a_2$ not passing through $a_1$, which would place $a_1$ on a cycle in $G$, a contradiction.

$\endgroup$
4
  • $\begingroup$ If the graph consists of four vertices $a,b,c,d$ with edges $(a,b),(a,c),(a,d)$, then it looks like your vertex $v$ doesn't exist. $\endgroup$
    – user136454
    Mar 1, 2019 at 19:14
  • $\begingroup$ @user136454, I've fixed that and another infelicity in the original answer. $\endgroup$
    – Ben Barber
    Mar 1, 2019 at 19:22
  • $\begingroup$ How do you formally prove that $v$ exists though? I don't think it's obvious from "since $A$ cannot be covered by a single path". $\endgroup$
    – user136454
    Mar 1, 2019 at 19:26
  • $\begingroup$ Throw away everything except the minimal subtree of $T$ containing $A$. If it isn't a path then it has a vertex of degree at least $3$, which we can take to be $v$. $\endgroup$
    – Ben Barber
    Mar 1, 2019 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.