Prove that following graph problem is in $L$
Let $N_k$ be the set of vertices at distance $k$ from 1. A graph satisfies the property if the sets $N_k$ are intervals, and $N_{k-1} &lt; N_k$ (every member of $N_{k-1}$ is smaller than every member of $N_k$). We will check this property inductively: assuming $N_{k-1}$ is known (starting with $N_0 = \{1\}$), we will show how to calculate $N_k$ and verify that it has the correct properties.

Suppose that $N_{k-1} = \{a,\ldots,b\}$. If $b = n$, we can stop. Otherwise, go over all neighbors of the vertices in $N_{k-1}$, and record the minimal and maximal indices $c,d$ encountered among those larger than $b$. Verify that $c = b+1$. Now go over all $e \in \{c,\ldots,d\}$, and verify that it is a neighbor of some vertex in $N_{k-1}$. If so, we have verified that $N_k = \{c,\ldots,d\}$, and can continue with $N_{k+1}$.

You can check that this algorithm can be implemented in logspace.