Number of graphs such that two sides remain connected after some edges are removed 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.
 A: Hint: There will either be a connection from top to bottom, or an open path from left to right.
How many configurations with open paths are there?
Further hint: In an $n\times m$ configuration there are $(n+1)m$ possible vertical edges and $m(n-1)$ possible horizontal edges. In the magic case where $m=n+1$, this works out as $(n+1)^2+n^2$ possible edges. That looks nicely symmetric, doesn't it?
A: This is a pictorial hint supplementing Henning Makholm’s answer.
Arrows are bridges, $O$s are their supports:
$$\begin{array}{|ccccccc|} \hline
\\
&\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\
&O&\longleftrightarrow&O&\longleftrightarrow&O&\longleftrightarrow&O&\\
&\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\
&O&\longleftrightarrow&O&\longleftrightarrow&O&\longleftrightarrow&O&\\
&\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\
&O&\longleftrightarrow&O&\longleftrightarrow&O&\longleftrightarrow&O&\\
&\updownarrow&X&\updownarrow&X&\updownarrow&X&\updownarrow\\
\\ \hline
\end{array}$$
Now arrows are possible seaways when the original bridges are broken:
$$\begin{array}{|ccccccc|} \hline
\\
&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\
&O&\updownarrow&O&\updownarrow&O&\updownarrow&O&\\
&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\
&O&\updownarrow&O&\updownarrow&O&\updownarrow&O&\\
&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\
&O&\updownarrow&O&\updownarrow&O&\updownarrow&O&\\
&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow&X&\longleftrightarrow\\
\\ \hline
\end{array}$$
Observe the symmetry between the two diagrams.
