First some definitions:
An edge path, or more simply a path, in a graph consists of an alternating sequence of vertices and edges $\{v_0,e_1,v_1,...,v_{n-1},e_n,v_n\}$ where $Ends(e_i) = \{v_{i-1},v_i\}$.
A backtrack is a path of the form $\{v,e,w,e,v\}$. A path is reduced if it contains no backtracks
A cycle or circuit is a nontrivial edge path whose first and last vertices are the same, but not other vertex is repeated.
A tree is a connected graph with no cycles.
Exercise 1.10. Prove that the following conditions on a connected graph $\Gamma$ are equivalent.
- $\Gamma$ is a tree.
- Given any two vertices $v$ and $w$ in $\Gamma$, there is a unique reduced edge from $v$ to $w$
- For every edge $e \in E(\Gamma)$, removing $e$ from $\Gamma$ disconnects the graph. (Note: Removing $e$ does not remove its associated vertices.)
- If $\Gamma$ is finite, then $\# V(\Gamma) = \# E(\Gamma) + 1$
I am just trying to show 1,2, and 3 are equivalent; but I am having some trouble. I am looking for a critique and help with finishing some of the proofs. Here's what I have so far:
First we prove (1) implies (2). Let $v,w$ be vertices in the tree $\Gamma$. Because $\Gamma$ is connected, there is edge path $\{v,e_1,v_1,...,v_{n-1},e_n,w\}$ from $v$ to $w$. Since $\Gamma$ is a tree, by definition it cannot contain cycles, so a fortiori it cannot contain any back tracks, so the edge path $\{v,e_1,v_1,...,v_{n-1},e_n,w\}$ must be reduced. Now we prove uniqueness. By way of contradiction, suppose that $\{v,f_1,w_1,...,w_{k-1},f_k,w\}$ is another edge path between $v$ and $w$. Then reversing the path and concatenating it with the former, we obtain $\{v,e_1,v_1,...,v_{n-1},e_n,w,f_k,w_{k-1},...,w_1,f_1,v\}$. But this is a nontrivial edge path from $v$ to $v$, that is, a cycle, so we have arrived at a contradiction.
Now we prove (2) implies (3). Let $e$ be some edge in the connected graph $\Gamma$. Being an edge, it must connect to vertices, call them $v$ and $w$. Clearly $\{v,e,w\}$ is a reduced path edge, since it isn't even long enough to have or be a backtrack. By (2), this is the only reduced path edge. Suppose there is another path from $v$ to $w$:
$$\{v,e_1,v_1,...,v_{i-1},e_i,v_i,e_{i+1},v_{i+1},e_{i+2},v_{i+2},...,v_{n-1},e_n,w\},$$ where $i=1,...,n$ is arbitrary. If $e_i \neq e_{i+1}$ and $v_{i-1} \neq v_{i+1}$, then, since $i$ was arbitrary, the above is a reduced path since it contains no backtracks, which is a contradiction. Hence there are multiple cases to consider. The first is that $e_i = e_{i+1}$ but $v_{i-1} = v_i$...don't know how to deal with this case...The second is that $v_{i-1} = v_{i+1}$ but $e_{i} \neq e_{i+1}$. If this is the case, then $\{v_{i-1},e_i,v_i\}$ and $\{v_{i+1},e_{i+1},v_i\}$ are two different reduced edge paths between, which contradicts (2). Finally, there is the case when $v_{i-1} = v_{i+1}$ and $e_i = e_{i+1}$...and there is where we can remove something to get a reduced path (if not, continue this process to get a reduced path...?)...not really sure how to finish this last case either
Now we argue (3) implies (1) contrapositively. If $\Gamma$ is not a tree, then there is a cycle $\{v_0,e_1,v_1,...,v_{n-1},e_n,v_n\}$ with $v_0 = v_n$. My thought was that removing $e_n$ would be the right move, but I am not so sure...I tried this, but the problem broke up into several very complicated cases, some of which I could not solve.
Edit: Okay I think my proof of uniqueness in my proof of "(1) implies (2)" is okay, so let me address the concern about backtracks. Suppose that the above path has a backtrack; that is, suppose that
$$\{...v_{i-i},e_i,v_i,e_{i+1},v_{i+1},e_{i+2},v_{i+2},e_{i+3}v_{i+3}...\}$$
with $v_i = v_{i+2}$ and $e_{i+1} = e_{i+2}$. Then by removing the edges $e_{i+1}$ and $e_{i+2}$, and vertices $v_{i+1}$ and $v_{i+2}$, we obtain
$$\{...,v_{i-i},e_i,v_i,e_{i+3},v_{i+3},...\},$$
which is a valid path between $v$ and $w$ because $Ends(e_{i+3}) = \{v_i,v_{i+3}\}$. This removes the backtrack from the given path. If it contains any other backtracks, these can be removed in the same way (there will be only finitely many, if any, so this removal can be done inductively).
Haven't worked out the other parts yet...will type them up when I get a chance.