Definitions and Theorems

$\newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} $

Section 8.1 Definitions and Theorems

Given a graph, a cycle is a circuit with no repeated edges. A tree is a connected graph with no cycles. A graph with no cycles and not necessarily connected is called a forest.

Let $G = (M, E)$ be a graph. The following are all equivalent:

$G$ is a tree.
For each pair of distinct vertices, there exists a unique path between them.
$G$ is connected, and if $e \in E$ then the graph $(V, E - {e})$ is disconnected.
$G$ contains no cycles, but by adding one edge, you create a cycle.
$G$ is connected and $|E| = |v| - 1\text{.}$

Let’s explore the following graph:

Let’s ask Sage if this graph is a tree.

If we remove an edge, we can see that the graph is no longer a tree.

However, we can see that the graph is still a forest.

If we add an edge, we can see that the graph contains a cycle and is no longer a tree.

Prev Top Next