the wait-for graph

The resource-allocation graph shows both processes and resources, but sometimes you only care about who is waiting on WHOM, not on what. So you collapse out the resources: draw just the processes, and put an arrow from one process to another if the first is waiting for something the second is holding. The result is a leaner diagram — the wait-for graph — that makes deadlock cycles jump out at a glance.

Precisely, the wait-for graph is obtained from the resource-allocation graph by removing the resource nodes and 'short-circuiting' through them: there is an edge Pi -> Pj exactly when Pi is waiting for a resource that Pj currently holds (i.e. Pi has a request edge to some resource R, and R has an assignment edge to Pj). A deadlock exists if and only if this graph contains a CYCLE, and detecting one is the classic graph problem of cycle detection, doable in time proportional to the number of nodes plus edges. The OS can maintain the graph incrementally and periodically run cycle detection on it.

The crucial, honest limitation: the wait-for graph is only valid for SINGLE-INSTANCE resource types. The collapse assumes 'waiting for resource R held by Pj' means 'waiting for Pj specifically.' But if R has several instances held by several processes, then Pi is waiting for ANY one of them to release, not for one particular Pj — so a single Pi -> Pj edge no longer captures the truth, and a cycle would not reliably mean deadlock. For multiple-instance systems you must drop the wait-for graph and use the more general matrix-based detection (the banker-style finish-and-reclaim sweep) instead.