Simple questions about a finite tree

130 Views Asked by At

Let $X$ be a finite tree (a contractible graph) which has at least one edge.

  1. There is a vertex of $X$ that meets only one edge of $X$.

  2. If we exclude the edge (and the vertex) in 1 from $X$, then $X$ is still a tree.

These two statements are intuitively clear, but I can't think of a way to prove these. Am I missing something?

2

There are 2 best solutions below

0
On BEST ANSWER
  1. If this were not the case, we would not have the Euler characteristic of a point (write the Euler characteristic in terms of the degree of each vertex).

  2. Quotienting out by a contractible subcomplex gives a homotopy equivalent space.

0
On

I'm missing some context for the definitions to work with them in-depth, but I suppose I can give a partial answer.

  1. Assume it is not true. Start at any vertex $v_0$ (with an edge to it). We can go over the edge to another vertex $v_1$ and from that to a vertex $v_2$, using another edge since $v_1$ doesn't have only one edge by our assumption. By repeating this process we get a sequence of vertices $(v_0,v_1,v_2,v_3,\ldots)$ with the property that for any $n\in\mathbb{N}_0$ we have $v_n\neq v_{n+1}$. Now two things can happen. The first is that all vertices are mutually distinct, i.e. $v_i\neq v_j$ for $i\neq j$, but then we would have infinite vertices in the graph, a contradiction. The other thing that can happen is that there is a minimal $n\in\mathbb{N}_0$ and $k\in\mathbb{N}$ such that $v_n=v_{n+k}$ (why?). But then the sequence $(v_n,v_{n+1},\ldots,v_{n+k})$ constitutes a cycle, which I suppose is a contradiction to the contractability of the graph. Hence our assumption was false and the statement 1. follows.
  2. This probably follows directly from your definitions. If the reduced graph wouldn't be a tree, that would mean that either a cycle appeared or there is a gap now, disconnecting the graph. But a gap wouldn't be closed when you add the vertex and edge again (because you would at most glue something at one end of the gap only), and the cycle wouldn't disappear either (since it doesn't contain the removed vertex or edge anyway).