----- > [!proposition] Proposition. ([[tree iff has n-1 edges]]) > A [[graph]] $G$ is a [[tree]] *if and only if* $G$ has $n-1$ edges, where $n$ is the number of nodes in $G$. > [!proof]- Proof. ([[tree iff has n-1 edges]]) > Let $G$ be a simple undirected graph with no self-loops, and suppose first that $G$ is a tree. Using this we want to show that $|E| = |V| - 1$ and that $G$ is connected. We proceed by induction on $|E|$. For the base case, let $|E|=0$. Then $G$ is a graph containing a single vertex (so $|V|=1$), and we have $|V| - 1 = 1 - 1 = 0 = |E|;$ as such, the base case holds. \ For the induction hypothesis suppose that the equality $|E| = |V| - 1$ holds for $|E|=k$; $k \geq 1$. We want to show now that it holds for $|E| = k+1$; that is, we want to show via the induction hypothesis that $k+1 = (|V|+1)-1 = |V|.$ > > We have that > $k = |V|-1.$ > Adding 1 to both sides yields$\begin{align*} > k+1 &= |V| - 1 +1 \\ > &= |V|,\end{align*}$ > as required to complete the induction. > \ > Conversely, suppose that $|E|=|V|-1$ and $G$ is connected. We want to show that $G$ is a tree. > \ > Suppose for the sake of contradiction that $G$ is not a tree. Then there exists at least one cycle in $G$, and we can remove edges from cycles until the resultant graph, $G'$, is a tree (has no cycles). Since $G'$ is a tree, it must have $|V|-1$ edges (as demonstrated in the first part of this proof), where $|V|$ is the number of vertices in both $G'$ and $G$. However, we showed before that $G'$ has fewer edges than $G$ — that is, that > $|E_G| < |E_{G'}|,$ > which is a contradiction since it implies that > $|V|-1 < |V|-1.$ > Thus $G$ has no cycles, and because $G$ is connected and has no cycles, $G$ is a [[tree]]. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```