This problem was actually from a programming problem, but it has more of a math flavor, so I am asking on Math stack exchange!
Problem: Initially, you are given a graph as in the first image, where red lines are edges and grey circles are vertices. You want to reach from the top platform to the bottom platform. Now, 0 or more edges are deleted from the graph. How many such configurations of graph are there so that there is a path from the top to the bottom?
The second image is an example of a configuration where it is possible to reach from the top to the bottom, and the third image is an example of a configuration where it is impossible.
The hint I got was that this problem is only solvable (or relatively easily solvable) only when the graph is N by N + 1 (the picture shows a graph of 3 by 4).
I don't really want an exact solution, but rather some hints on how to proceed (completely stuck at the moment). I tried setting up some recurrence relation, but had trouble doing so.