Try each one on paper first, then check a single step. That is worth far more than reading a finished solution.
Example 1 — using the handshaking lemma
A graph has vertices of degree 3,3,2,2,2. How many edges does it have?
- 1Each edge has two ends, so it adds 1 to two vertices' degrees.
- 2∑degrees=2×edgesThe handshaking lemma.
- 33+3+2+2+2=12
- 4Edges =212=6
- 5Note there are two odd-degree vertices — always an even number.A graph with exactly three odd vertices is impossible.
Example 2 — a forward and backward pass
Activities: A (3), B (4), C (2, after A), D (5, after B), E (3, after C and D). Find the project duration.
- 1Forward pass. A and B have no predecessors: ES =0, so EF =3 and 4.
- 2C follows A: ES =3, EF =5.
- 3D follows B: ES =4, EF =9.
- 4E follows both C and D: ES =max(5,9)=9.Take the MAXIMUM — everything must be finished.
- 5EF of E =9+3=12
- 6The project duration is 12.The largest earliest finish across all activities.
Example 3 — finding the critical path
For the same project, find the float of each activity and the critical path.
- 1Backward pass from LF(E) =12: LS(E) =9.
- 2D must finish by 9, so LS(D) =4. C must finish by 9, so LS(C) =7.
- 3A must finish by LS(C) =7, so LS(A) =4. B must finish by LS(D) =4, so LS(B) =0.Take the MINIMUM of the successors' latest starts.
- 4Float = LS − ES: A gives 4, B gives 0, C gives 4, D gives 0, E gives 0.
- 5Zero float means critical: B→D→E.
- 6Check: 4+5+3=12, the project duration ✓The critical path always equals the total.