Equivallent characterization of trees?

Question

I am a teacher of undergrad graph theory and we tend to invent some weird (and false) characterizations of trees and recently I stumbled upon this one.

Is the following true? $G$ is a tree if and only if $G$ is connected and between each pair of vertices of same degree, there is an unique path connecting them.

If we remove the connectivity condition, then any tree together with an isolated vertex is a counterexample. What if we add the connectivity?

Obviously if $G$ is tree, then the condition is true. But is it sufficient to show that $G$ is a tree? I tried to approach by contradiction that it contains a cycle. Given any circle $C$ in $G$, all vertices inside $C$ must necessarily have distinct degrees. But that's all I can come up with. Any ideas on how to proceed?

Edit: Some more thoughts. Assume, aiming for a contradiction, that $G$ contains a cycle $C$ and that $v_i, v_j$ are two vertices of the same degree (because for $|V|\geq 2$, it cannot happen that all vertices in $V$ have distinct degrees). $v_i,v_j$ cannot lie on a circle (not only they cannot be on C, but on any circle at all). Which in turn means that $v_i,v_j$ belong to distinct $2$-connected components. Now, Denote them $X,Y$. Assume the graph $G'$ whose vertex set consists of $2$-connected components of $G$ and there is an edge between $C_i$ and $C_j$ if and only if they share an articulation. Let $X,C_1,C_2,\ldots,C_k,Y$ be a path in $G'$ between $X$ and $Y$... Now if the components were nontrivial (i.e. contained a cycle), this would imply a contradiction, but $G$ could be just a path, so here I am stuck again ... There must be assumption about the location of the cycle $C$ w.r.t. $v_i, v_j$ and the components $X,Y$. Here I am stuck again.

Answer 1

This seems to be a correct characterization of trees, here is my proof of it (hope there is no mistake).

Let $G = (V, E)$ an undirected graph. Denote $(P)$ the property "$G$ is connected and between each pair of vertices of same degree, there is an unique path connecting them."

Suppose there exists a graph verifying $(P)$ without being a tree. Let $G$ be such a graph with the least possible number of edges. There exists two vertices $u, v\in V$ such that $\deg_G(u) = \deg_G(v)$. By $(P)$, there is a unique path $p = (v_1, …, v_k)$ from $u = v_1$ to $v = v_k$. Since there is a unique path between any two vertices of $p$, deleting the edges of $p$ will create $k$ connected components $C_1, …, C_k$, such that $C_i$ contains $v_i$ (otherwise, there would be more than one path between two vertices of the path).

• Fact 1: for each $i \in \{1, …, k\}$ such that $|C_i| > 1$, $C_i\setminus \{v_i\}$ contains a vertex $w$ such that $\deg_G(w) = 1$.

  • Proof of fact 1: suppose there is a $C_i$ of size $>1$ with no vertex of degree $1$ other than $v_i$. Then consider the graph $H$ obtained from $G[C_i]$ adding one (if $i = 1$ or $i = k$) or two (if $1 < i < k$) dummy vertices, adjacent only to $v_i$. In $H$, all non-dummy vertices have same degree as in $G$ (dummy vertices are here to insure that $v_i$ keeps the same degree). Moreover, there is a unique path between the two dummy vertices (if there are two).

    Note that there are very particular cases where $H$ has the same number of edges than $G$. This can only happen if both $u$ and $v$ are of degree $1$, and either $k = 2$, or $k = 3$ and $i = 2$. In the first case, $G$ is clearly a tree; in the second case, then $C_2$ contains two vertices of same degree $>1$ and we can use those vertices instead of $u$ and $v$.

    In all other cases, since $H$ satisfies $(P)$ and contains strictly less edges than $G$, it is a tree. By deleting the dummy vertices, it stays a tree. That means that $G[C_i]$ is a tree and contains at least two vertices of degree $1$. This is absurd given the hypothesis on $C_i$.

• Fact 2: let $C_i$ be a connected component of size $> 1$, and $w\in C_i, w\neq v_i$ a vertex of degree $1$. Then there is a unique path from $w$ to $v_i$.
  • Proof of fact 2: suppose there are at least two paths from $w$ to $v_i$. WLOG, suppose $i \neq 1$ (if $i = 1$, just swap the role of $1$ and $k$). Then consider $w'$ that is either $v_1$ if $\deg_G(v_1) = 1$ or a vertex $w'\in C_1, w'\neq v_1$ of degree $1$. Therefore, there would be at least two paths from $w$ to $w'$. This is absurd because $G$ satisfies $(P)$.
• Fact 3: for each $i \in \{1, …, k\}$, $G[C_i]$ is a tree.
  • Proof of fact 3: either $|C_i| = 1$ hence $G[C_i]$ is a trivial tree, or $|C_i| > 1$. If that's the case, consider the same construction $H$ as before. There is still a unique path between two vertices of same degree $> 1$. Given fact 2, there is a unique path between two vertices of degree $1$. Again, we conclude that $H$ is a tree, and that $G[C_i]$ (obtained by removing dummies) is a tree.

Adding the path $p$ to all $G[C_i]$, we cannot create a cycle, and therefore $G$ is a tree.

We conclude by contradiction that $G$ is a tree if and only if $G$ satisfies $(P)$.