Proof of tree property A graph is a tree iff it is connected and between all vertices of the same degree leads just one path.
How to prove it? I'm just learning for my exam and I'm pretty lost in proofs.
 A: First suppose $T$ is a tree and suppose for contradiction $\exists v \neq w$ in $V(T)$ (the set of vertices of $T$) such that $v$ and $w$ can be joined by two different paths $P_1 = (x_0 = v, x_1, x_2, x_3, ..., x_s = w)$, $P_2 = (y_0 = v, y_1, y_2, y_3, ..., y_r = w)$. Since $P_1 \neq P_2$, consider the first $i+1$ such that $x_{i+1} \neq y_{i+1}$ (so $x_i = y_i$) and the first $j, k \gt i$ such that $x_j = y_k$. Then we found a cycle $C = (x_i, x_{i+1}, ..., x_{j-1}, x_j = y_k, y_{k-1}, ..., y_{i+1}, y_i = x_i)$ in $T$, which is a contradiction. In particular, for any pair of vertices of same degree, there exists a unique path connecting them.
For this part, I'm not very sure of myself. Please correct me if I did something wrong.
Suppose $G$ is a connected graph such that for any two vertices of same degree $\exists$ only one path $P$ connecting them. Suppose for contradiction $G$ has a cycle $C$, made of at least $3$ vertices, who thus has degree at least $2$. For simplicity, we suppose this is the only cycle in $G$.
Notice that the degree of each vertices of the cycle must be distinct, otherwise, we have a contradiction to our hypothesis (we can find two different paths between two vertices of same degree). So one vertice of the cycle $C$, denoted $v$, has at least degree $3$, and another, denoted $w$, has at least degree $4$. So both have at least one edge $e_v = \{v = v_0, v_1\}$, $e_w = \{w = w_0, w_1 \}$ that leads outside the cycle. 
We must have $v_1 \neq w_1$, otherwise, we found a second cycle. Similarly, the only paths connecting $v_1$ and $w_1$ are the two paths $P^1_{v_1 \rightarrow w_1}$, $P^2_{v_1 \rightarrow w_1}$ given by the cycle, otherwise, we found another cycle. 
Then, from $v_1$, by choosing a neighbour different from $v_0$, and iterating this process by choosing a neighbour of $v_i$ different from $v_{i-1}$, since $G$ is finite, we will find a leaf $l_1$ (if the process doesn't stop, we found a cycle). We do the same process with $w_1$ and find $l_2 \neq l_1$. $l_1$ and $l_2$ have the same degree, namely $1$, but can be connected by two different paths : $P_{l_1 \rightarrow v_1} \cup P^i_{v_1 \rightarrow w_1} \cup P_{w_1 \rightarrow l_2}$, $ i= 1, 2$, because there are two paths connecting $v_1$ and $w_1$ : contradiction.
The idea of this proof is to find two vertices of same degree that surrounds the cycle, which gives a contradiction.
I don't really know how one can generalize this argument if, for contradiction, $G$ has more than one cycle, because it becomes quickly messy... But maybe someone will find a better proof...
However, this is much easier to prove : 
Now suppose $G$ is a connected graph such that for any two vertices $\exists$ only one path $P$ connecting them, then $G$ is a tree. Suppose for contradiction $G$ is not a tree, i.e. $G$ possesses a cycle as a subgraph, $C = (x_0, x_1, x_2, ..., x_r, x_{r+1} = x_0)$, $x_i \in V(G)$, $x_i = x_j \iff i = j$ or $\{i, j\} = \{0, r+1\}$ (the elements of the cycle are distinct except for the first and last one), $r \geq 2$ (a cycle has at least three elements). But then, take $x_1$ and $x_r$. You can find two different paths $P_1 = (x_r, x_{r+1} = x_0, x_1)$ and $P_2 = (x_1, x_2, ..., x_r)$ connecting them, which is a contradicition.
