2
The size of adjacency list representation is $\Theta(|E(G)| + |V(G)|)$, and not $\Theta(|E(G)|)$. For example, consider a graph with $n$ vertices and $0$ edges. The adjacency list corresponding to each vertex is empty. But storing the null pointer requires constant space for each vertex. Therefore, the size of the adjacency lists is $|V(G)|$ here.
2
The idea, in a nutshell, is that a graph does not contain an odd cycle iff it is 2-colorable (also known as bipartite).
Your algorithm attempts to find a 2-coloring of the graph. In each connected component, the coloring is unique once we fix the color of one of the vertices, since all neighbors of a white vertex are black and vice versa. The algorithm uses ...
1
The shortest path between vertices $A$ and $Z$ (where $A\ne Z$) is the minimum over all edges $A\to B_i$ of the weight of that edge plus the shortest path from $B_i$ to $Z$.
For general graphs, it isn't obvious how to optimize that, because some paths from $B_i$ to $Z$ may pass through $A$.
In a dag, that can't happen, and so there is an easy algorithm: ...
1
In the figure, the bottom four vertices of the graph are red-colored vertices.
$H$ has $5$ edges and $5$ vertices.
$H'$ has $6$ edges and $4$ vertices.
Only top voted, non community-wiki answers of a minimum length are eligible