search

jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.94k stars 1.02k forks source link

[Oops.] Inaccuracy in Lemma 6.1 #295

Open arbaazQureshi opened 3 months ago

arbaazQureshi commented 3 months ago

Please verify that the error is present in the most recent revision before reporting.

Chapter number or note title: Depth-first search

Page number: 230

Error description: In lemma 6.1, point b) must say u.pre < v.pre < v.post < u.post, and not u.pre <= v.pre < v.post <= u.post, if u is an ancestor of v.

Suggested fix (if any): Replace u.pre <= v.pre < v.post <= u.post with u.pre < v.pre < v.post < u.post

arbaazQureshi commented 3 months ago

Please correct this in the proof to this lemma too.