Exercise 4. Let D be a digraph. 1. Suppose that 8+ (D) ≤ 1 and let C be a cycle in D. Show that C is a directed cycle. 2. Let D be a digraph such that 8+ (D) ≥ 1. Let P be a directed path in D from a vertex x to a vertex y such that P is of maximum length. (a) Show that any out neighbor of y is on P. (b) Show that D contains a directed cycle. 3. Suppose that D is a strong digraph. Prove that 8+ (D) ≥ 1 and 8(D) ≥ 1.
Exercise 4. Let D be a digraph. 1. Suppose that 8+ (D) ≤ 1 and let C be a cycle in D. Show that C is a directed cycle. 2. Let D be a digraph such that 8+ (D) ≥ 1. Let P be a directed path in D from a vertex x to a vertex y such that P is of maximum length. (a) Show that any out neighbor of y is on P. (b) Show that D contains a directed cycle. 3. Suppose that D is a strong digraph. Prove that 8+ (D) ≥ 1 and 8(D) ≥ 1.
Related questions
Question
graph theory part 3
Transcribed Image Text:Exercise 4.
Let D be a digraph.
1. Suppose that 8+ (D) ≤ 1 and let C be a cycle in D. Show that C is a directed cycle.
2.
Let D be a digraph such that 8* (D) ≥ 1. Let P be a directed path in D from a vertex x to a vertex
y such that P is of maximum length.
(a) Show that any out neighbor of y is on P.
(b) Show that D contains a directed cycle.
3. Suppose that D is a strong digraph. Prove that 8+ (D) ≥ 1 and 8¯(D) ≥ 1.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps
