Your greedy approach works. Let's first find an abstraction of your problem that makes it easier to come up with a proof:
We have a family $F$ of sets of consecutive integers in $\{1,\ldots,k\}$ (we will call them intervals) that is closed under taking subintervals, i.e. for any $a\leq b\leq c\leq d$, if $\{a,\ldots,d\} \in F$, then $\{b,\ldots,c\} \in F$ also. Your problem is to find a minimum number of intervals in $F$ that covers $\{1,\ldots,k\}$. Converting from your graphic description to the set of intervals is not hard.
Another useful fact about $F$ is, as OP pointed out, that for every $i\in \{1,\ldots,k\}$, $\{i\}$ is in F.
My suggestion for a proof goes like this: Take any optimal solution $S^*$. Show that you can switch out each interval in $S^*$ with one in your greedy solution to obtain a set of equally few intervals. To this end, the fact that $F$ is closed under taking subintervals comes in handy.
Specifically, let $S$ be your greedy solution. We want to show for any $i$, the first (leftmost) $i$ intervals in $S$ cover at least as much as the first $i$ intervals in $S^*$. We can show this by induction.
For the base case, it is vacuously true that the first zero intervals in $S$ cover at least as much of $\{1,\ldots,k\}$ as the first zero intervals of $S^*$, which is nothing.
For the induction step, suppose that the hypothesis holds for the $i-1$ first intervals of $S$ and $S^*$, and we show that it is the case also for the i'th interval. Say that the first $i-1$ intervals in $S$ cover $\{1,\ldots,r\}$ and the first $i-1$ intervals in $S^*$ cover $\{1,\ldots,r^*\}$. By our hypothesis, $r \geq r^*$. $s^*_i$ then ends at some $t^*$. If $t^* > r$, then, since $F$ is closed under taking subintervals, there is an interval going from $r+1$ to $t^*$. And $s_i$ is clearly not smaller than this interval. If $t^* \leq r$, then we know that $\{r+1\}$ is an interval in $F$, and again, $s_i$ is clearly not smaller than this interval. Therefore, if $s_i$ ends at $t$, then $t \geq t^*$. This concludes the proof.
I hope this rather thorough writeup can be of any help into how one can design a proof that a greedy algorithm is optimal. It often comes down to showing how, at each step, we have an optimal subsolution. If you took any optimal solution and switched out the first few items for the items you found, you would end up with just as good a solution. In our case, we can, for any $i$, take the interval set $(s_1,\ldots,s_{i_1},s^*_i,\ldots,s^*_k)$. This is a solution (in fact, some elements may get covered twice or more, but this is not a problem).
