# Connectivity (graph theory) - proof

A graph $G$ has $n$ vertices. Prove that $G$ is connected if and only if we can find an injective sequence ($\ v_{1}...v_{n}$) such that for each $i>1$ there exists $j < i$ with $\ v_{i} v_{j}$ $\in$ E(G).

-

Proof by induction. $n=1$ both things are vacuously true. $n=2$ both statements hold if the two vertices are connected, both fail if they are not.
Suppose now $n>2$. If $G$ is connected, then some vertex $v$ can be removed without disconnecting the graph. proof $G\setminus \{v\}$ now has $n-1$ vertices, and remains connected. By induction, take the injective sequence, then put vertex $v$ at the end. If instead we have an injective sequence $(v_1, \ldots, v_n)$, then $(v_1,\ldots, v_{n-1})$ is an injective sequence and its corresponding graph $G\setminus \{v_n\}$ is connected. But now $v_n$ is connected to one of the other vertices by the property you are giving injective sequences.