TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 5

5) Show that each of the following four statements is equivalent to the statement ”T is a tree“:

1. Every two nodes of T are connected by exactly one path.
2. T is connected and α₀(T) = α₁(T) + 1.
3. T is a minimal, connected graph, i.e., deleting an edge destroys connectivity
4. T is a maximal, acyclic graph, i.e., adding an edge generates a cycle.

Theory

Tree

Solution

5.1.

Proof by contradiction

1. Assume: $\exists v,w$, where there are two or more paths between v and w

2. This implies there is a cycle. This contradicts with the definition of a tree

5.2.

Proof by induction

• $P(n_{0})$

$n_{0}=1$

T=(V={v},E={})

$\alpha _{0}(T)=|V|=1,$ $\alpha _{1}(T)=|E|=0$

• $P(n)\implies P(n+1)$

1. Add a vertex $u$ and connect it with an two existing, vertices $v,w$ with the edges $vu,uw$.

2. Now either:

2.a. |V|=1 and since there are no two vertces, then it is not possible to add two edges

2.b. In a tree there is always a path between two distinct vertices (as per definition it's connected). The edges $vu,uw$ introduce a second path. Use the same arguments as in 5.1

5.3

1. In a tree there is always a path between two distinct vertices $v,w$. If there is an edge $vw$, it is that path, and removing it contradicts with the definition.

5.4

Use the same arguments as in 5.2.2.b.

NOTE:" These are proves for "$P\implies T$ is a tree". To show equivalence ($a\iff b$) "$T$ is a tree $\implies P$" must also be proved

[1]