Question 1 Foundation
What is the degree of a vertex?
Answer. The number of edges meeting it.
A loop counts 2, since both of its ends are at the same vertex.
Graph Theory and Critical Path Analysis
Original questions written at exam standard. Work each one before you open the solution.
Difficulty
Question 2 Foundation
How many edges does a tree with 8 vertices have?
Answer.
A tree with vertices has exactly edges. One more would create a cycle; one fewer would disconnect it.
Question 3 Standard
A graph has degrees . How many edges?
Answer.
The degrees sum to 12, and the handshaking lemma gives edges.
Question 4 Standard
Describe Kruskal's algorithm in one sentence.
Answer. Add edges in increasing order of weight, skipping any that would create a cycle, until are chosen.
It builds up from scattered fragments, so a cycle check is needed at every step.
Question 5 Stretch
An activity has ES and LS . Find its float and say whether it is critical.
Answer. Float 4; not critical.
Float LS ES . Only zero-float activities are critical.
Question 6 Stretch
Why can a graph not have exactly three vertices of odd degree?
Answer. The sum of all degrees must be even, so odd degrees must occur in pairs.
The handshaking lemma makes the total twice the number of edges. Three odd values would sum to an odd number.