6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ You haven't used the unique path condition. $\endgroup$ Commented Nov 15, 2022 at 21:11
  • $\begingroup$ Yeah, how do i use it, that's my question. $\endgroup$ Commented Nov 15, 2022 at 21:14
  • 1
    $\begingroup$ Consider two vertices on a cycle ... $\endgroup$ Commented Nov 15, 2022 at 21:16
  • $\begingroup$ Yes, they must have distinct degrees, that's what I already observed. $\endgroup$ Commented Nov 16, 2022 at 8:59
  • 2
    $\begingroup$ @reinierpost I think it's better if you just say what you mean. Two vertices on the cycle have the same degree, and they do not have a unique path, hence the cycle is not a tree. That's not a counter-example. $\endgroup$
    – Pål GD
    Commented Nov 16, 2022 at 9:30

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$
11
  • $\begingroup$ So, we take the nontrivial component (as at most one is trivial), and there are atleast 3 components. Now, why should all vertices in C_i (except v_i) have degree (in G) greater than 1? I got stuck at that point. The rest is clear for me. $\endgroup$ Commented Nov 16, 2022 at 14:08
  • $\begingroup$ This is because of fact 1: only one component can contain a vertex of degree 1 which not a vertex of the cycle. $\endgroup$
    – Nathaniel
    Commented Nov 16, 2022 at 14:20
  • $\begingroup$ In graph theory, there is no restriction that $V$ and $E$ must be finite sets. It is still true that $G$ is a tree if and only if any two vertices are connected by a unique path; this is one of the standard definitions of a tree. It's not clear to me that this proof works in the infinite case, because there is no guarantee that there is a "largest" cycle. $\endgroup$
    – Pseudonym
    Commented Nov 16, 2022 at 14:20
  • 1
    $\begingroup$ @Nathaniel Ah, so there is at most one component with degree 1, and then in at most one there are degrees 1. So we pick the other one, where there are no degrees 1. $\endgroup$ Commented Nov 16, 2022 at 16:06
  • 1
    $\begingroup$ I think I found a mistake in the proof. The assumption that I get exactly k components, is false. Consider a C_6 with a chord. Then the chord connects two "components" after deleting the edges of C_6, but this does not contradict the fact that C_6 was the largest cycle. $\endgroup$ Commented Nov 16, 2022 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.