0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Exactly what definition of a tree are you using here? $\endgroup$ – Somos Mar 16 at 12:21
  • $\begingroup$ @Somos It is a $1$-dimensional CW complex which is contractible. $\endgroup$ – user302934 Mar 16 at 12:24
  • $\begingroup$ By "CW complex" I take it that you are using a topological space. So you are using a finite topological space? What do you mean by "finite" in this context? $\endgroup$ – Somos Mar 16 at 12:29
  • $\begingroup$ What if $X$ consists of a single vertex (and no edges)? How do the numbered items apply in this case? $\endgroup$ – paw88789 Mar 16 at 12:38
  • $\begingroup$ @Somos Here, finite tree means a tree with finitely many vertices and edges. $\endgroup$ – user302934 Mar 16 at 12:46
1
$\begingroup$
  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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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).
| cite | improve this answer | |
$\endgroup$

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