Proof. Let $P$ denote the transition matrix of random walk on $G$. The random walk is irreducible if for any vertices $x$ and $y$ there exists an integer $k$ such that $P^k(x, y)>0$. Note that $P^k(x, y)>0$ if and only if there exist vertices $x_0=x, x_1, \ldots, x_k=y$ such that $\prod_{i=0}^{k-1} P\left(x_i, x_{i+1}\right)>0$, i.e., $x_i \sim x_{i+1}$ for all $0 \leq i \leq k-1$. Therefore, the random walk is irreducible if and only if $G$ is connected.

Proof. The equivalence can be easily seen from Euler’s formula $m=n+l-2$ where $l$ denotes the number of faces of the graph, because any two of the following conditions will imply the other:
(1) $T$ is connected $\Longleftrightarrow m=n+l-2$;
(2) $T$ has no cycles $\Longleftrightarrow l=1$;
(3) $m=n-1$
Since this simple equivalence is a special case (and sometimes the starting point of the proof) of Euler’s formula, it should be proved without the use of the more general theorem. We provide a long yet elementary proof here. All three parts of the following proof are based on a simple operation, namely, removing one edge and one vertex at a time. We assume without loss of generality that $G$ has at least one edge. First we need a claim.
Claim: If each vertex of a graph $G$ has degree at least 2, then $G$ contains a cycle.
Start from any vertex $x_0$ of $G$ and we can find $x_1 \sim x_0$. Suppose we already find distinct $x_0, \ldots, x_i$ such that $x_0 \sim x_1 \sim \cdots \sim x_i$. Since $x_i$ has degree at least 2 , we can find $x_{i+1} \neq x_{i-1}$ such that $x_i \sim x_{i+1}$. If $x_{i+1}=x_j$ for some $j<i-1$, then we form a cycle. Otherwise we continue the process. The process must end because $G$ is finite, so $G$ contains a cycle.
(a) implies $(b)$ : Since $T$ is connected and contains no cycles, the claim implies that there exists a vertex of degree 1 in $T$. We delete this vertex and the attached edge from $T$, and the remaining object $T^{\prime}$ is still a connected graph with no cycles. We continue this process until the remaining graph has only one edge and thus two vertices. Since at each step we delete one edge and one vertex, it follows that $m=n-1$.

(b) implies (c): If there exists a vertex of degree 1 in $T$, we delete this vertex and the attached edge from $T$. Then the remaining object $T^{\prime}$ is still a connected graph with $m^{\prime}=n^{\prime}-1$ where $m^{\prime}$ is the number of edges and $n^{\prime}$ is the number of vertices. We continue this process until the remaining graph has no edges, or every vertex has degree at least 2 . The second case cannot happen because otherwise $n^{\prime} \leq m^{\prime}$ which is a contradiction. In the first case, $T$ cannot contain a cycle, because otherwise when we first delete an edge and one of its vertex in a cycle, the remaining object is no longer a graph.
(c) implies (a): If there exists a vertex of degree 1 in $T$, we delete this vertex and the attached edge from $T$. The remaining object $T^{\prime}$ is still a graph with no cycles and $m^{\prime}=n^{\prime}-1$. Note that if $T$ is not connected, then $T^{\prime}$ is not connected. We continue this process until the remaining graph has no edges, or every vertex has degree at least 2. The second case contradicts the claim because $T$ has no cycles. In the first case, because the relation $m=n-1$ is preserved, the remaining graph contains exactly one vertex and is thus connected. We conclude that $T$ is connected.