# Graph Edge

Learned in CS341.

White Path Lemma (5/19)

When we start exploring a vertex $v$, any $w$ that can be connected to $v$ by an unvisited path will be visited during $explore(v)$.

- This seems very similar to one of the lemmas from DFS with the iff, but this is cuz $explore$ is a new function introduced for DFS, which calls iself recursively

6/19

If $w$ is visited during $explore(v)$, there is a path $vâ†’w$.

- use the same proof as BFS by induction. Shouldnâ€™t this be a IFF?

9/19

All edges in $G$ connect a vertex to one of its descendants or ancestors.

Itâ€™s helpful to keep track of the start and finish times.

Then we talk about the cut vertex

Suppose we have a DFS forest. Edges of G are one of the following:

- tree edges
- back edges: from descendant to ancestor
- forward edges: from ancestor to descendant (but not tree edge)
- cross edges: all others

- These new categories of edges exist because we are now working in a directed graph. For an undirected graph, it would only be
*tree edges*and*back edges*

7/19

$G$ has a cycle if and only if there is a back edge in the DFS forest.

10/19

Suppose that $V$ is ordered using the reverse of the finishing order: $v<wâźşfinish[w]<finish[v]$.

This is a topological order.