How does the interactivity exactly work with the maze example?
Now imagine the maze has a large number of exits, all hard to find by luck, and the verifier tells you before you go in which exit they want to see you come out of. You don't know in advance which exit they will ask for. After you come out, they ask you for another one, and again you don't know in advance which one. These rounds are the interactivity.
Each time through, you have a soundness error's probability of finding the requested path by luck, i.e. winning the lottery kind of odds. The probability that you found all the exits the verifier asked for, is like winning the lottery multiple times in a row. Because you don't know which the verifier will ask for in advance, you can't take advantage of patterns in those requests to skew the combined probability in your favour. They are like independent random events: The probabilities multiply.
After N rounds, your probability of finding all the requested exits by luck is lottery kind of odds raised to the power of N. Pick a sufficiently large N and you have extreme probabilities like those used in other cryptography, numbers like 2⁻¹⁰⁰ or 2⁻²⁵⁶, which are so infeasibly unlikely they are similar to the probability of guessing someone's private key or guessing a SHA-256 hash preimage. We trust this demonstrates you know the maze, even though there's an astronomically unlikely possibility that you guessed right every time.
If they consider two graphs drawn differently as different graphs, they should clarify it from the start … and maybe not pose it as a graph problem.
Alice gives Bob a graph. Bob can ask Alice to show the bijection (hard) or show a path (hard) but not both.
Say Alice and Bob do this 40 times.
Can you see how Bob should be convinced that Alice is giving him isomorphic graphs and that she knows a path through the graph? Otherwise Alice would have failed to answer one of his questions along the way.