Diagram:
Question:
Is it possible to infer the out-degree of vertex 4 in $G^+$ from the information given?
I was completely stumped on what to do here. I looked at the solution:
Yes. There is a walk from vertex 4 to every other vertex in the graph in $G^2$. If there is a walk from 4 to vertex x in $G^2$, then there is a walk from 4 to x in $G$ which implies that $(4, x)$ is an edge in $G^+$.
But I still don't understand the logic. How does the fact that you can draw a walk from $4$ to any other vertex in $G^2$ suggest that you can do the same in $G$?
First of all, make sure not to confuse edges with walks.
I suppose $G^2$ is the graph that has an edge from $i$ to $j$ if and only if there is a walk of length $2$ from $i$ to $j$ in the original graph $G$
I also assume that $G^+$ is the graph that shows an edge from $i$ to $j$ if there is a walk of any length from $i$ to $j$ in the original graph (this is the same as taking the transitive closure of $G$).
Well, then it makes sense that if there is a walk in $G^2$ from $i$ to $j$, then there is a walk of length $2n$ in $G$ from $i$ to $j$, and hence there will be an edge from $i$ to $j$ in $G^+$
For example, in $G^2$ there is a walk from $4$ to $2$: $4 \rightarrow 3 \rightarrow 1 \rightarrow 2$
Now, the edge of $4$ to $3$ in $G^2$ means that there is a walk of length $2$ in the original $G$. We don't know which vertex this walk goes through, but it has to be some vertex in $G$. Same for the edge in $G^2$ from $3$ to $1$, and from $1$ to $2$, so we know there is a walk in $G$ that looks like:
$4 \rightarrow ? \rightarrow 3 \rightarrow ? \rightarrow 1 \rightarrow ? \rightarrow 2$
So, there is a walk from $4$ to $2$ in $G$, and therefore an edge from $4$ to $2$ in $G^+$