Posted by: jpend9 | October 3, 2010

## Trees recap

(Guest post by JP Endaya)

On Friday’s lecture we began discussing more about trees. We said that a tree is a connected undirected graph with no cycles.

We took a look at a rooted tree, which is an upside down tree,  for the structure of a tree.

We pick any vertex as root and let the rest of the tree hang under gravity.

On the lecture slide graph, we declared a vertex a parent if it directly precedes another vertex(which in turn is a child).

• SG’s parent = AC
• AC’s child = SG

We were then presented with a question: How many rooted trees can an n vertex tree have?

The answer is n because, as mentioned earlier, we can pick any vertex as a root.

For the rest of the discussion we tried to “Prove n vertex tree has n-1 edges.”

CLAIM: Let G=(V,E) be a tree with |V|=n. Then |E|=n-1.

Proof idea:

• Root G at some vertex
• Direct each edge towards the root
• Each (directed) uniquely corresponds (“starts” off) from a non-root
• => |E| = # non-roots = n-1

Proof:

• Pick any r ϵ V as root
• Root G at r
• Direct each edge towards r

Lemma:

• Each directed edge has a unique “starting” point and vice versa
• => for every e ϵ E → v ϵ V \ {r}
• => for every v ϵ V\ {r} → e ϵ E
• => |E| = |V\ {r} | = n-1

Proof idea for Lemma: By contradiction

• Every edge has one vertex, r in our example, as its starting point.
• Contradiction: a cycle u, x~r~y, u where “~” represents a path between x and r and y and r and both x and y are connected to u.

We did not prove the Lemma but began looking at connection on large graphs and on the slide were asked if s and t are connected  . We considered the brute-force algorithm where we list all possible vertex sequences between s and t and check if any is a path between s and t. We also agreed that there is n^n such sequences.