MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

Six tasks p,q,r,s,t,up,q,r,s,t,u have prerequisites pp before qq, pp before rr, qq before ss, rr before ss, rr before tt, ss before uu (and whatever these force transitively). For how many of the (62)=15\binom{6}{2}=15 pairs of tasks is the relative order of the two tasks NOT forced – that is, either could legally be scheduled before the other?