I'm reviewing previous exams of Graph Theory and found this question:
Consider a strongly connected directed graph G and its underlying undirected graph G*. Prove that λ(G*) ≥ 2.
But I am confused. How can a directed graph have an undirected subgraph? Doesn't "digraph" imply that all edges are directed?
The "underlying undirected graph," $~G^*$, is just $G$ without the edges having any direction. Since $G$ is strongly connected, every pair of vertices in $G^*$ lies on some cycle in $G^*$. Hence deleting a single edge cannot disconnect the graph. Therefore $\lambda(G^*)\geq2$.