7.4: Trees

Last updated
Save as PDF

Page ID: 182005

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

A row of trees with no leaves. — Figure $\PageIndex{1}:$ In graph theory, graphs known as trees have structures in common with live trees. (credit: “Row of trees in Roslev” by AKA CJ/Flickr, public Domain)

Learning Objectives

Describe and identify trees.
Determine a minimum spanning tree for a connected graph.
Solve application problems involving trees.

We saved the best for last! In this last section, we will discuss arguably the most fun kinds of graphs and trees. Have you ever researched your family tree? Family trees are a perfect example of the kind of trees we study in graph theory. One of the characteristics of a family tree graph is that it never loops back around because no one is their own grandparent!

What Is A Tree?

Whether we are talking about a family tree or a tree in a forest, none of the branches ever loops back around and rejoins the trunk. This means that a tree has no cyclic subgraphs or is acyclic. A tree also has only one component. So, a tree is a connected acyclic graph. Here are some graphs that have the same characteristics. Each of the graphs in figure $\PageIndex{2}$ and figure $\PageIndex{2}$ are a tree.

Three graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. — Figure $\PageIndex{2}:$ Graphs T, P, and S

Six graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. Graph Z has 12 vertices. The edges are a b, a c, a d, a e, a f, a g, a h, h i, c j, e k, and k l. Graph C has 14 vertices. The edges are m n, n z, n o, o r, o p, o x, o y, p y, p x, p s, p t, p u, p q, p v, and p w. Graph L has 26 vertices. The edges are f q, f t, f s, f e, e o, e p, p z, e d, d m, m v, d n, n y, d c, c k, k u, c l, l k, c b, b i, i t, b j, j w, b a, b g, and b h. — Figure $\PageIndex{3}:$ Number of Vertices and Edges in Trees vs. Other Graph

Applications of Tree Graphs

Tree structures appear everywhere because they efficiently organize information. Here are the most common and important uses:

Folders and subfolders on a computer form a tree.
Communication networks
Shows relationships between generations.
Company Organization Chart

Definition: Characteristic of a Tree

There are no loops or closed paths.
Every pair of vertices is connected by exactly one path.
The number of edges is one less than the number of vertices. If tree has $n$ vertices, It must have $n-1$ edges.
Every edge in a tree is a bridge.

Your Turn $ \PageIndex{1} $: Family Relationship

Example $\PageIndex{2}$: Identifying Trees

Identify any trees in Figure $\PageIndex{4}.$ If a graph is not a tree, explain how you know.

Three graphs. Graph M has 7 vertices. The edges are a b, b f, f g, f c, b c, b d, and d e. Graph N has 6 vertices. The edges are I j, I h, l k, and l m. The edges, I j, and l k intersect each other. Graph P has 6 vertices. The edges are s t, s r, r q, q p, and p o. — Figure $\PageIndex{4}:$ Graphs M, N, and P

Answer

Graph M is not a tree because it contains the cycle (b, c, f).

Graph N is not a tree because it is not connected. It has two components, one with vertices h, i, j, and another with vertices k, l, m.

Graph P is a tree. It has no cycles, and it is connected.

Example $\PageIndex{3}$: Exploring Characteristics of Trees

Use Graphs I and J in Figure $\PageIndex{5}$ to answer each question.

Two graphs. Graph I has six vertices: a, b, c, d, e, and f. Edges connect a b, b c, b e, d e, and e f. Graph J has seven vertices: g h, i, j, k, l, and m. Edges connect g h, h i, j h, j l, k l, and l m.

Figure $\PageIndex{5}:$ Graphs I and J

$1.$ Which vertices are in each of the components that remain when edge be is removed from Graph I?

$2.$ Determine the number of edges and the number of vertices in Graph J. Explain how this confirms that Graph J is a tree.

$3.$ What kind of cycle is created if edge im is added to Graph J?

Answer

$1.$ When edge be is removed, there are two components that remain. One component includes vertices a, b, and c. The other component includes vertices d, e, and f.

$2.$ There are seven vertices and six edges in Graph J. This confirms that Graph J is a tree because the number of edges is one less than the number of vertices.

$3.$ The pentagon (i, h, j, l, m) is created when edge im is added to Graph J.

Your Turn $ \PageIndex{3} $: Identify Tree

Who Knew?: Graph Theory in the Movies

In the 1997 film Good Will Hunting, the main character, Will, played by Matt Damon, solves what is supposed to be an exceptionally difficult graph theory problem, “Draw all the homeomorphically irreducible trees of size $n =$ 10.” That sounds terrifying! But don’t panic. Watch this great Numberphile video to see why this is actually a problem you can do at home!

Spanning Trees

Suppose that you planned to set up your own computer network with four devices. One option is to use a “mesh topology” like the one in Figure $\PageIndex{9},$ in which each device is connected directly to every other device in the network.

Four illustrations represent the common network configurations. The first illustration represents mesh topology. Six computers are interconnected. The second illustration represents a ring topology. Five computers are connected in a ring. The third illustration represents star topology. A computer at the center is connected to five computers surrounding it. The fourth illustration represents tree topology. Two branches arise from a horizontal bus. Each branch has a computer at the center connected to five computers surrounding it. — Figure $\PageIndex{6:}$ Common Network Configurations

The mesh topology for four devices could be represented by the complete Graph A₁ in Figure $\PageIndex{7}$ where the vertices represent the devices, and the edges represent network connections. However, the devices could be networked using fewer connections. Graphs A₂, A_3, and A₄ of Figure $\PageIndex{7}$ show configurations in which three of the six edges have been removed. Each of the Graphs A₂, A₃ and A₄ in Figure $\PageIndex{7}$ is a tree because it is connected and contains no cycles. Since Graphs A₂, A_3, and A₄ are also subgraphs of Graph A₁ that include every vertex of the original graph, they are also known as spanning trees.

Four graphs. Graph A 1 has four vertices: a, b, c, and d. The edges are a b, b d, d c, c a, a d, and b c. Graph A 2 has four vertices: a, b, c, and d. The edges are a b, b c, and c d. Graph A 3 has four vertices: a, b, c, and d. The edges are a b, a c, and c d. Graph A 4 has four vertices: a, b, c, and d. The edges are a b, a c, and a d. — Figure $\PageIndex{7}:$ Network Configurations for Four Devices

By definition, spanning trees must span the whole graph by visiting all the vertices. Since spanning trees are subgraphs, they may only have edges between vertices that were adjacent in the original graph. Since spanning trees are trees, they are connected, and they are acyclic.

So, when deciding whether a graph is a spanning tree, check the following characteristics:

All vertices are included.
No vertices are adjacent that were not adjacent in the original graph.
The graph is connected.
There are no cycles.

What is a Spanning Tree?

A spanning tree of a graph is a sub-graph that includes all the vertices of the original graph and has no cycles (because it is a tree).

Why use a Spanning Tree?

Because it connects all points with no redundancy and uses the least number of edges, it is used in:

Designing efficient communication networks
Reducing the cost of wiring or cabling
Optimizing routes in transportation

Example $\PageIndex{4}$: Identifying Spanning Trees

Use Figure $\PageIndex{8}$ to determine which of graphs M₁, M₂, M₃, and M₄, are spanning trees of Q.

Five graphs. Graph Q has six vertices: a, b, c, d, e, and f. The edges are a b, a c, a d, b d, d f, c d, c e, c f, and e f. Graph M 1 has six vertices: a, b, c, d, e, and f. The edges are a b, b d, d c, c e, f, and f d. Graph M 2 has six vertices: a, b, c, d, e, and f. The edges are a b, a d, d f, f e, and e c. Graph M 3 has six vertices; a, b, c, d, e, and f. The edges are b d, d f, a f, f e, and e c. Graph M 4 has six vertices: a, b, c, d, e, and f. The edges are a b, c e, e f, and f d. — Figure $\PageIndex{8}:$ Graphs Q, M₁, M₂, M_3, and M₄

Answer

$1.$ Graph M₁ is not a spanning tree of Graph Q because it has a cycle (c, d, f, e).

$2.$ Graph M₂ is a spanning tree of Graph Q because it has all the original vertices, no vertices are adjacent in M₂ that weren’t adjacent in Graph Q, Graph M₂ is connected, and it contains no cycles.

$3.$ Graph M₃ is not a spanning tree of Graph Q because vertices a and f are adjacent in Graph M₃ but not in Graph Q.

$4.$ Graph M₄ is not a spanning tree of Graph Q because it is not connected.

So, only graph M₂ is a spanning tree of Graph Q.

Your Turn $ \PageIndex{4} $: Identify Spanning Tree

Constructing a Spanning Tree Using Paths

Suppose that you wanted to find a spanning tree within a graph. One approach is to find paths within the graph. You can start at any vertex, go any direction, and create a path through the graph, stopping only when you can’t continue without backtracking, as shown in Figure $\PageIndex{9}.$

A graph with 23 vertices and 35 edges. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here. — Figure $\PageIndex{9}:$ First Phase to Construct a Spanning Tree

Once you have stopped, pick a vertex along the path you drew as a starting point for another path. Make sure to visit only the vertices you have not visited before, as shown in Figure $\PageIndex{10}.$

A graph with 23 vertices and 35 edges. Ten edges are highlighted in blue. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here. — Figure $\PageIndex{10}:$ Intermediate Phase to Construct a Spanning Tree

Repeat this process until all vertices have been visited as shown in Figure $\PageIndex{11}.$

The end result is a tree that spans the entire graph as shown in Figure $\PageIndex{12}.$

A graph with 23 vertices and 22 edges. — Figure $\PageIndex{12}:$ The Resulting Spanning Tree

Notice that this subgraph is a tree because it is connected and acyclic. It also visits every vertex of the original graph, so it is a spanning tree. However, it is not the only spanning tree for this graph. By making different turns, we could create any number of distinct spanning trees.

Revealing Spanning Trees

Another approach to finding a spanning tree in a connected graph involves removing unwanted edges to reveal a spanning tree. Consider Graph D in Figure $\PageIndex{13}.$

Graph D has 10 vertices. The vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and I j. — Figure $\PageIndex{13}:$ Graph D

Graph D has $10$ vertices. A spanning tree of Graph D must have $9$ edges, because the number of edges is one less than the number of vertices in any tree. Graph D has $13$ edges so $4$ need to be removed. To determine which $4$ edges to remove, remember that trees do not have cycles. There are four triangles in Graph D that we need to break up. We can accomplish this by removing $1$ edge from each of the triangles. There are many ways this can be done. Two of these ways are shown in Figure \(\PageIndex{14}.\

Four graphs depict removing edges from graph D. In the first graph, the vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and i j. The edges, a c, e f, g h, and b j are shown in dashed lines. The second graph is the same as that of the first with edges, a c, e f, g h, and b j removed. In the third graph, the vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and i j. The edges, a c, a g, b f, and b i are shown in dashed lines. The fourth graph is the same as that of the first with edges, a c, a g, b f, and b i removed. — Figure $\PageIndex{14}:$ Removing Four Edges from Graph D

Example $\PageIndex{5}$: Removing Edges to Find Spanning Trees

Use the graph in Figure $\PageIndex{15}$ to answer each question.

Graph V has 9 vertices. The vertices are labeled from a to i. The edges are f c, f a, c a, c d, d a, a b, b e, e h, h i, I g, and g b. — Figure $\PageIndex{15}:$ Graph V

$1.$ Determine the number of edges that must be removed to reveal a spanning tree.

$2.$ Name all the undirected cycles in Graph V.

$3.$ Find two distinct spanning trees of Graph V.

Answer

$1.$ Graph V has nine vertices, so a spanning tree for the graph must have 8 edges. Since Graph V has $11$ edges, $3$ edges must be removed to reveal a spanning tree.

$2.$ (a, c, d), (a, c, f), (a, d, c, f), and (b, e, h, i, g)

$3.$ To find the first spanning tree, remove edge ac, which will break up both of the triangles, remove edge cf, which will break up the quadrilateral, and remove be, which will break up the pentagon, to give us the spanning tree shown in Figure $\PageIndex{16}.$

A graph has 9 vertices. The vertices are labeled from a to i. The edges are f a, c d, d a, a b, b g, g i, I h, and h e. — Figure $\PageIndex{16}:$ Spanning Tree Formed Removing *ac, cf*, and be

A graph has 9 vertices. The vertices are labeled from a to i. The edges are f c, c d, c a, a b, b e, e h, b g, and g i. — Figure $\PageIndex{16}:$ Spanning Tree Formed Removing *ac, cf*, and be

Your Turn $\PageIndex{5}$: Constructing Spanning Trees

Construct two distinct spanning trees for the graph in Figure $\PageIndex{18}.$

Graph L has 11 vertices and 19 edges. The graph resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines. — Figure $\PageIndex{18}:$ Graph L

Answer: Two possible solutions are given in Figure $\PageIndex{19}$ and Figure $\PageIndex{20}.$

$Two graphs depict removing edges from graph L. The first graph has 11 vertices and 19 edges. It resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines. 6 edges are in green, 2 edges are in purple, and 2 edges are in blue. Green represents phase 1, blue represents phase 2, and purple represents phase 3. The second graph is the final tree. The black edges from the first graph are removed.$
Figure $\PageIndex{19}:$ First Spanning Tree for Graph L

$Two graphs depict removing edges from graph L. The first graph has 11 vertices and 19 edges. It resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines. 6 edges are in green, 2 edges are in purple, and 2 edges are in blue. Green represents phase 1, blue represents phase 2, and purple represents phase 3. The second graph is the final tree. The black edges from the first graph are removed.$
Figure $\PageIndex{20}:$ Second Spanning Tree for Graph L

Minimum Spanning Tree (MST) and Kruskal’s Algorithm

In many applications of spanning trees, the graphs are weighted, and we want to find the spanning tree of the least possible weight. For example, the graph might represent a computer network, and the weights might represent the cost involved in connecting two devices. So, finding a spanning tree with the lowest possible total weight, or minimum spanning tree, means saving money! The method that we will use to find a minimum spanning tree (MST) of a weighted graph is called Kruskal’s algorithm. The steps for Kruskal’s algorithm are:

Kruskal's Algorithm: To Find MST

Step 1: Choose any edge with the minimum weight of all edges.

Step 2: Choose another edge of minimum weight from the remaining edges. The second edge does not have to be connected to the first edge.

Step 3: Choose another edge of minimum weight from the remaining edges, but do not select any edge that creates a cycle in the subgraph you are creating.

Step 4: Repeat step $3$ until all the vertices of the original graph are included and you have a spanning tree.

Where is MST used?

MSTs help design networks that connect all nodes at the minimum cost. Some examples include

Cable TV distribution networks, Internet wiring, fiber-optic networks, Telephone and communication networks
Electrical power grids
Cheapest road connections between cities, Railway routes, Pipeline networks (water, gas, oil)
Airline route optimization (connecting hubs with minimal cost)

Example $\PageIndex{6}:$ Using Kruskal’s Algorithm

A computer network will be set up with six devices. The vertices in the graph in Figure $\PageIndex{21}$ represent the devices, and the edges represent the cost of a connection. Find the network configuration that will cost the least. What is the total cost?

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. — Figure $\PageIndex{21}:$ Graph of Network Connection Costs

Answer

A minimum spanning tree will correspond to the network configuration of the least cost. We will use Kruskal’s algorithm to find one. Since the graph has six vertices, the spanning tree will have six vertices and five edges.

Step 1: Choose an edge of least weight. We have sorted the weights into numerical order. The least is $$100.$ The only edge of this weight is edge AF as shown in Figure $\PageIndex{22}.$

Search

Text Color

Text Size

Margin Size

Font Type

Applications of Tree Graphs

Definition: Characteristic of a Tree

Your Turn \( \PageIndex{1} \): Family Relationship

Example \(\PageIndex{2}\): Identifying Trees

Example \(\PageIndex{3}\): Exploring Characteristics of Trees

Your Turn \( \PageIndex{3} \): Identify Tree

Who Knew?: Graph Theory in the Movies

Example \(\PageIndex{4}\): Identifying Spanning Trees

Your Turn \( \PageIndex{4} \): Identify Spanning Tree

Example \(\PageIndex{5}\): Removing Edges to Find Spanning Trees

Your Turn \(\PageIndex{5}\): Constructing Spanning Trees

Kruskal's Algorithm: To Find MST

Example \(\PageIndex{6}:\) Using Kruskal’s Algorithm

Your Turn \( \PageIndex{6} \): Find MST

Your Turn \( \PageIndex{7} \): Definitions