Does the runtime keep a directed graph representing which goroutine waits for which somewhere? If so, could you point me to the relevant place in the source code?
I have not professionally coded in Go but noticed it has several nice features when I played with it.
You can check the Go source and easily find out: it happens in this function, which is called in various places where the program might enter a deadlock state.
The relevant part is that the runtime gets the number of open OS threads, and checks how many of them are actually running code. There are a few more checks, but that's basically it. Whenever you run a blocking operation - such as as locking a mutex when it's already been locked elsewhere, or receiving from an empty channel - the scheduler will try to make the thread do the work of another goroutine. If none can be found, it enters an idle state.
Basically, the scheduler always tries to find code that is waiting to be ran. If none can be found, then it's a deadlock situation.
This of course excludes cases of, i.e., goroutines which are running time.Sleep, which although are "idling", there's a thread actively checking when they are ready to be run. In other words, they are not dependent on other parts of the program to start being "runnable" again (such as is the case for mutexes).
Short: The runtime scheduler, responsible for sharing execution time of OS threads between goroutines, realizes that all goroutines are waiting forever or waiting on other goroutines and concludes a deadlock.
Imagine a scenario where goroutine A fetches pages from the internet, sending them through channel C over to goroutine B. Goroutine A has nothing to do until goroutine B sends to channel C, so goroutine A is asleep waiting on goroutine A. Goroutine B is blocked waiting on a system call (HTTP request) to complete, so goroutine B is not waiting on other goroutines. Now, if you insert any operation that makes goroutine B wait on other goroutines (like receiving from channel D), goroutine B will be put to sleep, and since all other goroutines (just goroutine A really) are already asleep, we conclude a deadlock.
Long: Read Go scheduler.