*(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.

## Leave a Reply