Let G = (V, E) be a graph Provide a proof that shows G is connected iff there exists a walk that passes through every vertex in G.
I understand that since it's a iff statement, there should be two separate proofs in the form of "If A, then B" and "If B, then A", where the first part is assumed to be true and I have to prove the second part. I'm just not sure what to do from there.
Suppose $G$ is connected. Then by definition of connectivity, there exists an $i, j$ path for all $i, j \in V(G)$. A path is a walk where no vertices are repeated. Constructing a union of such walks $W_{v_{i}, v_{i+1}}$ for all $i \in \{1, ..., n-1\}$ will produce a walk through all vertices of $G$.
Now suppose an $i, j$ walk exists for all $i, j \in V(G)$. A walk may repeat vertices. Let $i, j \in V(G)$. So let $W_{ij}$ be an $i, j$ walk. If there is no repeated vertex in $W$, then $W$ is a path and we are done. Otherwise, let $v$ be a repeated vertex in $W_{ij}$ and let $v_{i} \to v_{i+1}$ represent the subwalk between the consecutive instances of $V$. We contract this walk to $v_{i+1}$ (so if we have $v_{i} \to x \to y \to ... \to v_{i+1}$, we remove everything from $v_{i}$ up to $v_{i+1}$. That is, we keep $v_{i+1}$). The last instance of $v$ in the walk is kept. We apply this procedure for all such $v \in W_{ij}$ that are repeated. By finiteness of the walk, this procedure always terminates for each vertex. And so we are left with a path. Thus, we have constructed an $i, j$ path in $G$. Our choices of $i, j$ were arbitrary, and so the result holds for all $i, j \in V(G)$.
Edit: I updated the forward direction above. The modified backward direction is actually pretty similar to what I have above.
So we suppose there exists a walk through all vertices in $G$. Let $W$ be such a walk. For each pair of vertices $i, j$, we find the first occurrence of $i$ on $W$ and then find the first occurrence of $j$ nearest to $i$. We apply the contraction procedure for every repeated vertex along the $i, j$ sub-walk. This gives us an $i, j$ path. Thus, there exists an $i, j$ path for all vertices $i, j$. And so $G$ is connected.