[proofplan] We prove the three-way equivalence by a cycle of four implications $(1) \Rightarrow (2) \Rightarrow (1) \Rightarrow (3) \Rightarrow (1)$, which is more economical than all six directions and establishes the equivalence among the three conditions. The argument is structural: it rests on the fundamental dichotomy that an edge $xy$ either lies on a cycle (in which case $xy$ can be rerouted around the cycle, so deleting $xy$ preserves connectivity) or it does not (in which case adding or removing $xy$ strictly changes the cycle set). The rerouting argument invokes [Walk Contains Path](/theorems/2007) to upgrade the walk produced by rerouting to a genuine path, which is what connectivity demands. [/proofplan] [step:Prove $(1) \Rightarrow (2)$ by deriving a cycle from redundant connectivity] Assume $G$ is a tree: $G$ is connected and acyclic. We must show $G$ is minimally connected, i.e., that for every $xy \in E(G)$ the graph $G - xy$ is disconnected. Fix $xy \in E(G)$ and suppose for contradiction that $G - xy$ is connected. Then in $G - xy$ there is an $x$–$y$ walk, and by [Walk Contains Path](/theorems/2007) this walk contains an $x$–$y$ path $P = x_0, x_1, \ldots, x_k$ with $x_0 = x$, $x_k = y$, all $x_i$ distinct, and every edge $x_{i-1} x_i$ lying in $E(G - xy) \subseteq E(G)$. Since $xy$ is absent from $G - xy$ and $P$ lies in $G - xy$, the edge $xy$ does not appear among the edges of $P$, so in particular $k \ge 2$ (a path of length $1$ from $x$ to $y$ would be the edge $xy$ itself). Now append the edge $xy$ to $P$ to obtain the closed sequence \begin{align*} C = x_0, x_1, \ldots, x_k, x_0. \end{align*} All vertices $x_0, \ldots, x_k$ are pairwise distinct, each consecutive pair $x_{i-1} x_i$ is an edge of $G$, the closing pair $x_k x_0 = yx$ is an edge of $G$ (the edge $xy$ itself), and $k + 1 \ge 3$, so $C$ is a cycle in $G$. This contradicts the acyclicity of $G$. Hence $G - xy$ is disconnected. [guided] The overall shape of the argument is: we assume the conclusion fails, find an alternative route from $x$ to $y$ avoiding the edge $xy$, and combine that route with $xy$ to close up a cycle — contradicting acyclicity. The only subtlety is that "alternative route" must be a **path**, not a walk, in order to form a cycle; this is where [Walk Contains Path](/theorems/2007) enters. Assume $G$ is a tree and fix an edge $xy \in E(G)$. Suppose, aiming for a contradiction, that $G - xy$ is connected. Connectedness of $G - xy$ means: for any two vertices (in particular, for $x$ and $y$) there is a walk between them in $G - xy$. Let $W$ be any such $x$–$y$ walk in $G - xy$ — such a $W$ exists and has at least one edge because $x \neq y$. We need a **path**, not merely a walk, because a cycle must have distinct vertices. The theorem [Walk Contains Path](/theorems/2007) applies: it takes an $x$–$y$ walk with $x \neq y$ and extracts an $x$–$y$ path as a subsequence. Applied to $W$ inside $G - xy$, it yields a path \begin{align*} P = x_0, x_1, \ldots, x_k, \qquad x_0 = x,\ x_k = y, \end{align*} whose edges all lie in $E(G - xy)$ (since $P$ is a subsequence of $W$, its edges are consecutive pairs in $W$, and $W$'s edges are in $E(G - xy)$). In particular, **none of the edges $x_{i-1} x_i$ is the edge $xy$**, because that edge was deleted. Together with $x_0 = x$ and $x_k = y$ this forces $k \ge 2$: if $k = 1$, the single edge of $P$ would be $x_0 x_1 = xy$, which we just excluded. Now we close the cycle. Consider the closed sequence \begin{align*} C = x_0, x_1, \ldots, x_k, x_0. \end{align*} Let us check $C$ is a cycle in $G$. A cycle is a closed walk whose internal vertices are distinct and whose length is at least $3$: 1. Internal vertices: $x_0, x_1, \ldots, x_k$ are distinct (since $P$ is a path). 2. Edges: $x_{i-1} x_i \in E(G - xy) \subseteq E(G)$ for $1 \le i \le k$, and the closing edge $x_k x_0 = yx = xy$ lies in $E(G)$ by assumption. 3. Length: the length (number of edges) is $k + 1 \ge 3$, since $k \ge 2$. So $C$ is a cycle in $G$. But $G$ is acyclic by the hypothesis that $G$ is a tree. Contradiction. Therefore $G - xy$ is disconnected, and since $xy$ was arbitrary, $G$ is minimally connected. [/guided] [/step] [step:Prove $(2) \Rightarrow (1)$ by rerouting around any putative cycle] Assume $G$ is minimally connected. By definition $G$ is connected, so we need only show $G$ is acyclic. Suppose for contradiction $G$ contains a cycle \begin{align*} C = v_0, v_1, \ldots, v_{r-1}, v_0, \qquad r \ge 3, \end{align*} with the $v_i$ pairwise distinct and each $v_{i-1} v_i \in E(G)$ (indices modulo $r$). Pick any edge of $C$, say $xy := v_0 v_1$. We claim $G - xy$ is still connected, contradicting minimal connectivity. Let $u, v \in V(G)$ be arbitrary. Since $G$ is connected, there is a $u$–$v$ walk $W$ in $G$. If $W$ does not use the edge $xy$, then $W$ is already a $u$–$v$ walk in $G - xy$. Otherwise, $W$ uses $xy$ some number of times; we construct from $W$ a $u$–$v$ walk $W^\star$ in $G - xy$ by replacing each occurrence of $xy$ by the **rest-of-cycle arc** \begin{align*} A = v_1, v_2, v_3, \ldots, v_{r-1}, v_0 \end{align*} (traversed forward from $y = v_1$ to $x = v_0$) or its reverse $A^{\mathrm{rev}} = v_0, v_{r-1}, \ldots, v_1$ (from $x$ to $y$), whichever orientation agrees with the direction in which $W$ crosses $xy$. Every edge of $A$ and $A^{\mathrm{rev}}$ lies in $E(C) \setminus \{xy\} \subseteq E(G) \setminus \{xy\} = E(G - xy)$, so $W^\star$ is a $u$–$v$ walk in $G - xy$. Thus for every $u, v \in V(G)$ there is a $u$–$v$ walk in $G - xy$, so $G - xy$ is connected. This contradicts the assumption that $G - xy$ is disconnected, so $G$ has no cycle. [guided] Minimal connectivity asserts that every edge is a **bridge** — deleting any edge disconnects the graph. To contradict this, we must exhibit a single edge whose deletion preserves connectivity. Cycles provide exactly such edges: any edge on a cycle has a detour, namely the rest of the cycle. Assume $G$ is minimally connected. Connectedness is part of the hypothesis, so we only need acyclicity. Suppose for contradiction $G$ has a cycle \begin{align*} C = v_0, v_1, \ldots, v_{r-1}, v_0, \qquad r \ge 3. \end{align*} Choose any edge of $C$ to delete, say $xy := v_0 v_1$ (the others would work identically). We will show $G - xy$ is connected — contradicting minimal connectivity, which demands that $G - xy$ be disconnected. The idea: the cycle $C$ has two arcs between $x$ and $y$. One arc is the single edge $xy$. The other arc, the "rest of the cycle," is \begin{align*} A : y = v_1 \to v_2 \to v_3 \to \cdots \to v_{r-1} \to v_0 = x, \end{align*} a walk from $y$ to $x$ whose edges are $v_1 v_2, v_2 v_3, \ldots, v_{r-1} v_0$. All these edges are edges of $C$ distinct from $xy$, so they all remain in $G - xy$. Now we show connectivity of $G - xy$. Fix any $u, v \in V(G)$. Since $G$ is connected, take any $u$–$v$ walk $W$ in $G$. Two cases: 1. If $W$ does not use the edge $xy$, then $W$ is already a $u$–$v$ walk in $G - xy$. 2. If $W$ uses $xy$, replace each crossing of $xy$ by the arc $A$ (or its reverse $A^{\mathrm{rev}} = v_0, v_{r-1}, \ldots, v_1$) depending on whether $W$ traverses $xy$ from $x$ to $y$ or from $y$ to $x$. The result $W^\star$ is a sequence of vertices with every consecutive pair forming an edge; all those edges lie in $E(G - xy)$ since we substituted cycle edges that are not $xy$. So $W^\star$ is a $u$–$v$ walk in $G - xy$. (We do not need $W^\star$ to be a path; a walk is enough for connectivity. The statement "every $u$–$v$ walk contains a $u$–$v$ path" from [Walk Contains Path](/theorems/2007) would upgrade $W^\star$ to a path if we needed one, but here the walk itself certifies connectivity.) Since $u, v$ were arbitrary, $G - xy$ is connected. This contradicts minimal connectivity of $G$. So no cycle $C$ exists, i.e., $G$ is acyclic. Combined with the given connectivity, $G$ is a tree. [/guided] [/step] [step:Prove $(1) \Rightarrow (3)$ by closing a $u$–$v$ path with a new edge] Assume $G$ is a tree. We show $G$ is maximally acyclic: acyclicity is part of the hypothesis, and it remains to show that for every $xy \notin E(G)$ with $x \neq y$, the graph $G + xy$ contains a cycle. (If $x = y$ the "edge" $xy$ is a loop; in the simple-graph setting loops are not admitted, so we need only consider $x \neq y$.) Fix such $x, y$. Since $G$ is connected, there is an $x$–$y$ walk in $G$, and by [Walk Contains Path](/theorems/2007) there is an $x$–$y$ path $P = x_0, x_1, \ldots, x_k$ with $x_0 = x$, $x_k = y$, $x_i$ pairwise distinct, and $x_{i-1} x_i \in E(G)$. Since $xy \notin E(G)$, the path $P$ has length $k \ge 2$: if $k = 1$ its single edge would be $x_0 x_1 = xy$, contradicting $xy \notin E(G)$. Append the new edge to close up: the closed sequence \begin{align*} C = x_0, x_1, \ldots, x_k, x_0 \end{align*} has pairwise distinct internal vertices $x_0, \ldots, x_k$, every consecutive edge $x_{i-1} x_i$ lies in $E(G) \subseteq E(G + xy)$, the closing edge $x_k x_0 = yx = xy$ lies in $E(G + xy)$ by construction, and its length is $k + 1 \ge 3$. So $C$ is a cycle in $G + xy$. [/step] [step:Prove $(3) \Rightarrow (1)$ by contradicting maximal acyclicity with a disconnection] Assume $G$ is maximally acyclic. Acyclicity is part of the hypothesis, so it remains to show $G$ is connected. Suppose for contradiction $G$ is disconnected. Then there exist $x \neq y$ with no $x$–$y$ walk in $G$; in particular $xy \notin E(G)$ (an edge would itself be an $x$–$y$ walk of length $1$). By maximal acyclicity, the graph $G + xy$ contains a cycle $C$. We claim $C$ must use the edge $xy$. If not, $C$ is a cycle of $G + xy$ using only edges of $E(G)$, hence $C$ is a cycle of $G$, contradicting the acyclicity of $G$. So $C$ uses $xy$. Write $C = x, y, u_1, u_2, \ldots, u_s, x$ (re-indexing to start at $x$ and traverse the edge $xy$ first), with the internal sequence $x, y, u_1, \ldots, u_s$ pairwise distinct and every consecutive pair an edge of $G + xy$. The remaining sequence $y, u_1, u_2, \ldots, u_s, x$ is a walk from $y$ to $x$; its edges are $yu_1, u_1 u_2, \ldots, u_{s-1} u_s, u_s x$, none of which equals $xy$ (because the vertices $x, y, u_1, \ldots, u_s$ are pairwise distinct, so no pair among the remaining edges has both endpoints in $\{x, y\}$). Therefore all these edges lie in $E(G)$, and $y, u_1, \ldots, u_s, x$ is a $y$–$x$ walk in $G$. Reversing this walk gives an $x$–$y$ walk in $G$, contradicting the choice of $x, y$ as vertices with no $x$–$y$ walk. Hence $G$ is connected. [guided] Maximal acyclicity is dual to minimal connectivity. Minimal connectivity says every edge is "needed for connectivity"; maximal acyclicity says every non-edge is "needed to avoid a cycle." The proof strategy mirrors the dual: we assume $G$ is disconnected, find a missing edge $xy$ between two components, note that maximal acyclicity forces $G + xy$ to contain a cycle, and extract from that cycle a path in $G$ connecting $x$ and $y$ — contradicting disconnectedness. Assume $G$ is maximally acyclic. Acyclicity is given, so we establish connectedness. Suppose for contradiction $G$ is disconnected, so there are vertices $x \neq y$ with no $x$–$y$ walk in $G$. Since a single edge $xy$ would itself form a walk of length $1$, we must have $xy \notin E(G)$. Maximal acyclicity then says $G + xy$ contains a cycle, call it $C$. Why must $C$ traverse the new edge $xy$? Because $C$ is a cycle of $G + xy = (V, E(G) \cup \{xy\})$, every edge of $C$ lies in $E(G) \cup \{xy\}$. If none of the edges of $C$ were the edge $xy$, then all edges of $C$ would lie in $E(G)$, making $C$ a cycle of $G$. But $G$ is acyclic. So $C$ uses $xy$. Now re-index $C$ to begin with the edge $xy$: there exist pairwise distinct vertices $x, y, u_1, u_2, \ldots, u_s$ in $V(G)$ such that \begin{align*} C = x, y, u_1, u_2, \ldots, u_s, x \end{align*} is the cycle, and every consecutive pair is an edge of $G + xy$. The edge $xy$ appears only as the first edge (since $x$ and $y$ each appear only once among the internal vertices). The remaining edges \begin{align*} y u_1,\ u_1 u_2,\ \ldots,\ u_{s-1} u_s,\ u_s x \end{align*} all have distinct endpoint pairs that are not $\{x, y\}$, so none of them is the edge $xy$. Therefore each of them lies in $E(G + xy) \setminus \{xy\} = E(G)$. Reading off the second part of $C$ we get \begin{align*} y, u_1, u_2, \ldots, u_s, x, \end{align*} a sequence of vertices in $V(G)$ with every consecutive pair an edge of $G$. This is a $y$–$x$ walk in $G$. Reversing it — walks have no intrinsic orientation — yields an $x$–$y$ walk in $G$. But we assumed no such walk exists. Contradiction. So $G$ is connected, and combined with the given acyclicity, $G$ is a tree. [/guided] [/step] [step:Close the logical cycle] We have established $(1) \Rightarrow (2) \Rightarrow (1)$ and $(1) \Rightarrow (3) \Rightarrow (1)$. Composing these implications yields $(1) \Leftrightarrow (2)$ and $(1) \Leftrightarrow (3)$, and by transitivity $(2) \Leftrightarrow (3)$. So all three conditions are pairwise equivalent. [/step]