1
$\begingroup$

This is an excerpt proving that if a graph $G$ is connected and has one more vertex than edge, then it is acylic.

Suppose $|V|=n$ and that $G$ has a $k$-cycle. This cycle has $k$ vertices and edges, hence $G$ has $n-k$ additional vertices. Each of these vertices has a minimal path to the cycle. By minimality, each of these paths contains an edge not appearing in any other. Hence we have at least $n-k$ new edges, so at least $n$ in total, contradicting the assumed equality.

Can someone explain how exactly minimality implies each path has an edge not on any other? It seems to me entirely possible that a minimal path is entirely contained in another - simply have one vertex adjacent to the cycle, and another one adjacent to the previous one but not directly to the cycle.

The proof is $3\implies 4$ here.

$\endgroup$
1
  • $\begingroup$ Yeah, seems that you're reasoning is correct and the proof is wrong. $\endgroup$
    – arkeet
    Sep 24 '16 at 18:29
2
$\begingroup$

Let $v$ be a vertex not belonging to the cycle $c_1c_2\cdots c_k$. Then by connectedness there exists a path the form $v_0v_1\cdots v_r$ with $v_0=v$ and $v_r=c_i$. Among all such paths for $v$, pick one that minimizes $r$. As $v$ is not in the cycle, $r\ge 1$. Associate $v$ with the first edge $vv_1$ of one such shortest path. If §w§ is another vertex not belonging to the cycle, we likewise associate it with the first edge $ww_1$ of a shortest path $ww_1\cdots w_s$ for $w$. The claim is that $vv_1$ is not the same edge as $ww_1$. Indeed, for these to be equal, we need $v_1=w$ and $w_1=v$. But then either $v_1\cdots v_r$ is a shorter path for $w$ or $w_1\cdots w_s$ is a shorter path for $v$, contradiction. Hence the above association of vertices with edges is injective.

$\endgroup$
5
  • $\begingroup$ But I don't understand - what if $v$ is adjacent to the cycle and $w$ is adjacent to $v$ but not the cycle? Isn't this a counterexample to what the linked proof writes? There is a minimal path entirely contained in another... $\endgroup$ Sep 24 '16 at 18:24
  • 1
    $\begingroup$ Right, the linked proof is wrong by your argument. But this small modification fixes it. Briefly put, the first edge in each path is different for different vertices. $\endgroup$
    – arkeet
    Sep 24 '16 at 18:31
  • 1
    $\begingroup$ @combinarcotics: Your example does show that the argument given in the PDF is incorrect as stated. The correct claim is that it’s possible to choose an edge in each of the $n-k$ paths in such a way that we choose a different edge for each path. One of these edges may belong to more than one of the paths, but it gets chosen for only one of them Hagen’s argument shows how this can be done. $\endgroup$ Sep 24 '16 at 18:34
  • 1
    $\begingroup$ @BrianM.Scott thanks (again!). $\endgroup$ Sep 24 '16 at 18:42
  • $\begingroup$ @combinarcotics: You’re welcome! $\endgroup$ Sep 24 '16 at 18:43

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.