let P be the set of paths from room 1 to the exit (room 0)
let E be the bag of edges in P
let freq(e) := the number of times e is found in E
order elements of E by freq(e), giving a "table" as such:

Edge     Frequency
------------------
E        4
F        2
G        1
H        1
I        1
.
.
.

let E' be the set of the top most edges in the table such that forall e in E', sum(freq(e)) = |P|
eliminate the edges in E' to trap the spy
the answer to the question is |E'|