Show that if $U$ is a non-trivial module in a tree $T$, then every vertex of $U$ has degree $1$ in T.

Question

I was wondering if anybody could help with this exercise from my graph theory lecture notes. Intuitively it seems fairly clear to me that what I want to show must be true, however I am rather unfamiliar in proofs involving modules as they were only introduced to me in this course.

I attempted considering a vertex of degree at least $2$ belonging to $U$ and considering its neighbours but unfortunately I wasn't able to progress very far, any help would be appreciated thanks!

Answer 1

Relevant definitions:

• A tree is a connected graph with no cycles.
• A module is a set $U \subseteq V(G)$ such that for any two vertices $u_1, u_2 \in U$, the neighbors of $u_1$ in $V(G) \setminus U$ are the same as the neighbors of $u_2$ in $V(G) \setminus U$.

Let $U = \{u_1, u_2, \dots\}$ be a module in a graph $G$ and let $W = \{w_1, w_2, \dots\}$ be the set of vertices in $V(G) \setminus U$ adjacent to the vertices of $U$. The module is trivial if $U = \varnothing$ or $|U|=1$ (when there's nothing to check), and also if $W = \varnothing$ (when $U$ induces a connected component of $G$ - the whole graph, in the case of a tree).

There are two cases in which a cycle appears (you should draw out the graph with $U$, $W$, and the edges between them and check this):

1. If $|U|>1$ and $|W|>1$, then we get a cycle.
2. If $W \ne \varnothing$ and there are $u_i, u_j \in U$ with an edge $u_i u_j$, then we get a cycle.

If we're in a tree, then neither of these can happen. So the only remaining possibility for a nontrivial module is $|W|=1$ and $U$ is an independent set. You should check that in this case, every vertex of $U$ has degree $1$.