Here are two excises about safe vertex deletions
------------------------------------------------

> 
> 5-28. An articulation vertex of a graph G is a vertex whose deletion disconnects G. Let G be a graph with n vertices and m edges. Give a simple O(n + m) algorithm for finding a vertex of G that is not an articulation vertex—i.e. , whose deletion does not disconnect G.
> 
> 
> 5-29. Following up on the previous problem, give an O(n + m) algorithm that finds a deletion order for the n vertices such that no deletion disconnects the graph. (Hint: think DFS/BFS.)
> 
> 
> 

---

**For 5-28, here is my thought:**

I will just do a dfs, but not complete. **The very first vertex** which finished being processed will be a non-articulation vertex as it must be a leaf, or a leaf with a back edge pointing back to its ancestor (it is also not a articulation vertex).

**For 5-29**

I am not yet sure how to do it nicely. What comes into my mind is that in the graph, any vertex in a cycle can't deleted safely. Also, if there is no cycle, then deleting vertex backwards up from a dfs tree is also safe.

Could anyone give me some hints or tell me whether my thinking is correct or wrong?