Don't understand this graph definition

Question

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows:

Given a graph $G= \langle V_G, E_G \rangle$, we can construct the $H(G)=\langle V_H, E_H\rangle$ as follows: $$V_H = V_G\times\{0,1\}$$ $$E_H = \{((v,0),(v,1))|v\in V_G\}\cup\{((x,1),(y,0))|(x,y)\in E_G\}.$$ Say that we have a graph $\langle G,u,v\rangle$ where $G$ is some directed graph, which contains vertices $u$ and $v$ then $H(G)$ can be used to find the smallest number of nodes that must be removed from $G$ to separate $u$ to $v$, meaning there will be no simple path from $u$ to $v$.

I really don't understand what's going on here, partly because I can't visualise $H(G)$. I assume we'd get some bipartite graph and maybe apply Edmonds-Karp only because the flow networks sections is succinct and there's not much else in this chapter. Could someone tell/show me what $H(G)$ is doing exactly and why this result is true. Much appreciated.

EDIT:

I've added some images of the what I got for $H(G)$ for some simple graphs. I understand that the function will transform a graph into a bipartite graph. But, how does this graph tell us the minimum number of vertices that have to be removed so there doesn't exists a simple path from $u$ to $v$ in the original graph? I'm perhaps wondering if it is a maximum matching problem in disguise.

Answer 1

D.W.'s advice to consider some small examples is excellent. Two great examples to start with are an isolated vertex and a single edge! Once you can how the construction transforms vertices and edges, you know what happens to the building blocks.

Also, some familiarity with the basics of these constructions helps. In particular, any time you see "Let the vertex set of the new graph be $V\times S\,$" for some set $S$, you should think: "Take a copy of $V$ for every element of $S$, and label each copy with the element it's associated with." So, here, the vertex set of $H$ is two copies of $G$'s vertex set: one labelled $0$ and one labelled $1$. Now, look at the edges. The first set of edges says, "For every vertex $v\in G$, add an edge from copy $0$ to copy $1$." The second set says, "For every edge $(x,y)\in G$, add an edge from copy $1$ of $x$ to copy $0$ of $y$."

Answer 2

As David already pointed out, the construction replaces each vertex $v$ with two vertices $(v,0)$ and $(v,1)$ and an edge from $(v,0)$ to $(v,1)$ (I'll call this edge $e_v$ in the following).

Now, since all incoming edges of $v$ are connected to $(v,0)$ and all outgoing edges are connected to $(v,1)$, the edge $e_v$ will have exactly the flow of the node $v$ in the original graph.

You probably were presented an algorithm that finds a minimal edge cut in the lecture. It should be obvious how this gives a minimal vertex cut for $G$, if only edges $e_v$ are in the cut. If the cut contains edges from the second set, it is less obvious, but we may still translate this into a set of vertices to remove. (We have more than one choice about which vertex to remove for any such edge.) I'll leave it to you to figure out the details.