0
$\begingroup$

I don't know if that's the most accurate title.

I'm trying to prove that one property of trees implies another without using any of the other properties.

This is for homework. But I'm really just curious if the proof was this easy or if someone more clever can find glaring holes. I will cite any help I receive. I'm a CS guy that doesn't have much experience writing proofs.

Conjecture:

The graph G is connected, but removing any edge disconnects the graph implies that any two vertices in G are connected by a unique simple path.

My proof is this:

Suppose that the G is not connected by a unique simple path. Then there must exist some edge that could be removed without resulting in a disconnected graph.

Does this work?

$\endgroup$
  • $\begingroup$ The idea is right, but you may want to be a little bit more explicit as to why there must exist some edge whose removal does not disconnect $G$. Assuming otherwise and deriving a contradiction would probably be the way to go. $\endgroup$ – Josh Chen Feb 3 '16 at 11:34
1
$\begingroup$

You need to add a lot more detail and clean up some inaccuracies.

First, the negation of the conclusion isn’t that $G$ is not connected by a unique simple path: it’s that there are two vertices, $u$ and $v$, of $G$ that are not connected by a unique simple path. We’re assuming that $G$ is connected, so $u$ and $v$ are connected by at least one simple path; if this path isn’t unique, there must be another one. Call these two paths $P$ and $Q$. Since they’re not the same path, there must be an edge $e$ that’s in one of them, say $P$, but not in the other. You want to show that removing $e$ leaves $G$ connected, since that would prove the contrapositive of the desired implication and hence the implication itself.

Removing $e$ doesn’t disconnect $u$ from $v$, since it doesn’t affect the path $Q$, but that doesn’t show that $G$ is still connected: you also need to show that it doesn’t disconnect any other pair of vertices. That takes a bit of work. One way to do it is to show that if $x$ is any vertex of $G$ other than $u$ and $v$, there is a path from $x$ to $u$ that does not use $e$. (Why is this enough to show that $G-e$ is still connected?) You know that there is some simple path $R$ in $G$ from $x$ to $u$. Suppose that it includes $e$.

  • To complete the argument, explain how to use $Q$ and $P-e$ to replace $R$ with a path from $x$ to $u$ that does not include $e$.
$\endgroup$
  • $\begingroup$ Yes, I felt like I was lacking some rigor. Allow me some time to roll this around in my head. $\endgroup$ – noel Feb 3 '16 at 11:49

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.