Spanning Trees and Their Properties | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 11.4 Free with a free account

Spanning Trees and Their Properties

Discrete Mathematics · Chapter 11: Trees, Spanning Trees, and Minimum Cost NetworksSection 11.4 · lesson 74 of 878 min · free with a free account

← Sorting with Trees: Benefits and LimitationsNext lesson: Kruskal's Algorithm for Minimum Spanning Trees →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Every connected network hides a tree - usually many.

  • Define spanning trees and spanning forests
  • Prove: connected exactly when a spanning tree exists
  • Compute a graph's circuit rank
  • Count spanning trees of complete graphs

Transcript

Everything said in the video, section by section (1,208 words). Read along, or search it.

Trees, Spanning Trees, and Minimum Cost Networks

Spanning Trees and Their Properties

Every connected network hides a tree inside it. Usually more than one, and sometimes an astonishing number. This section defines spanning trees, ties their existence directly to connectivity, and counts how many a graph can have.

The Opening Problem

Fiber for 5 Neighborhoods

A municipal broadband project needs to connect five neighborhoods with fiber-optic cable. Engineers survey the terrain and find nine feasible routes between pairs of neighborhoods. Laying all nine would connect everyone, but it would be wasteful. Once every neighborhood can reach every other, more cable adds redundancy, not new reach. So the real question is narrower. What's the smallest set of routes that still connects all five? Any such minimal set is a spanning tree of the graph of feasible routes. This section asks what those are, and how many there are to choose from. Which one is cheapest to build is the subject of the next two sections.

11.4.1

What Is a Spanning Tree?

Let G be a connected graph. A spanning tree of G is a subgraph T with three properties. First, it includes every vertex of G. Second, it uses only edges that belong to G. And third, it's itself a tree, connected and acyclic. If G is disconnected, the analogous structure, one spanning tree per connected component, is called a spanning forest. Nothing requires the spanning tree to be unique. Almost any connected graph with a cycle has several, each keeping all the vertices, and discarding just enough edges to break every cycle.

Worked Example

One Extra Edge, 3 Spanning Trees

Here's a small example. G has a hub, A, joined to B, C, D and E, plus one extra edge, B C, which closes the triangle A, B, C. G has five vertices and five edges, one more than the four a spanning tree needs. That single extra edge is what makes more than one spanning tree possible. Edges A D and A E are the only way to reach D and E. So both must be in every spanning tree. The only freedom is which edge of the triangle to leave out. Any one of the three works, since removing one edge from a cycle never disconnects a graph. So G has exactly three spanning trees. Each keeps all five vertices, uses only G's edges, and has exactly four edges.

11.4.2

Connected Exactly When a Spanning Tree Exists

Spanning trees and connectivity are two ways of saying the same thing. A graph is connected if and only if it has a spanning tree. One direction is quick. If G has a spanning tree, any two vertices are joined by a path in that tree, and every edge of that path is an edge of G. So G is connected. For the other direction, suppose G is connected. As long as some cycle remains, delete any one of its edges. Deleting an edge on a cycle never disconnects the graph, since the rest of the cycle still joins its two endpoints. So the graph stays connected after every deletion. The process must stop, since each step removes an edge from a finite graph. And it can only stop when no cycle is left. At that point the graph is connected and acyclic, a spanning tree.

Redundant Edges

n - 1 Edges, Plus the Circuit Rank

Since a spanning tree is a tree, section eleven point one applies directly. Every spanning tree of an n-vertex graph has exactly n minus one edges, however many edges the original graph has. The edges beyond those n minus one are redundant for connectivity. Each one closes a cycle. A connected graph with m edges on n vertices has exactly m minus n minus one, in parentheses, such redundant edges. That's called the graph's circuit rank. The hub graph has five edges on five vertices, so its circuit rank is one, matching its single triangle. And any tree has circuit rank zero.

11.4.3

Cayley's Formula

How many spanning trees can a graph have? For one important family, there's an exact, remarkably simple formula. Cayley's formula, from eighteen eighty-nine. The complete graph K n, with every pair of its n vertices joined, has exactly n to the n minus two spanning trees. We won't prove it here. The standard argument encodes each spanning tree as a sequence of n minus two vertex labels, called a Prüfer sequence, and shows the encoding is a bijection. Each position can be any of n labels, so there are n to the n minus two sequences. A completely different proof uses the Matrix-Tree Theorem, from Kirchhoff in eighteen forty-seven. It counts the spanning trees of any connected graph, complete or not, as a determinant of a matrix built from the degrees and adjacencies.

Worked Example

16 Spanning Trees of $K_4$

Take n equals four. Cayley's formula gives four squared, sixteen spanning trees for K four. Every spanning tree of K four has three edges. And on four labeled vertices, there are only two tree shapes. One is a straight path, like one, two, three, four. There are four factorial over two, which is twelve, ways to label a path, since a path read backwards is the same path. The other is a star, one hub joined to the other three. There are four choices for the hub. Twelve plus four is sixteen, consistent with the formula. And the count grows fast. One, three, sixteen, one hundred twenty-five, and already one thousand two hundred ninety-six at n equals six.

Back to the Broadband Survey

Too Many to List

Cayley's formula counts spanning trees of complete graphs only. The broadband survey found nine of the ten possible routes among five neighborhoods. That graph isn't complete, so one hundred twenty-five doesn't apply. Counting its spanning trees directly gives seventy-five. The Matrix-Tree Theorem, applied to the survey's actual routes, gives the same count. Either way, the practical point stands. The number of candidate spanning trees explodes as a network grows. That's why the next two sections develop algorithms that build one good spanning tree directly, rather than listing every candidate and comparing them.

11.4.4

Spanning Trees in Practice

The broadband problem is one instance of a pattern throughout network design. Whenever sites can be linked by more connections than strictly needed, the connections actually used to guarantee reachability form a spanning tree. Power grid planning has the same shape. Substations often have several feasible routes between them, and the minimal set of lines keeping every substation powered is a spanning tree. Computer networks show it too. Switches with redundant cabling rely on a spanning tree structure, and network engineers use exactly that term. It disables just enough links that traffic can't circulate endlessly around a cycle. In every case, the recognition task is the same. Check that every required site is included, that only real connections are used, and that the result is connected and free of cycles.

Takeaways

Every Vertex, No Cycles, n - 1 Edges

To summarize. A spanning tree of a connected graph touches every vertex, uses only the graph's own edges, and is connected and acyclic. A graph is connected exactly when it has a spanning tree. And every spanning tree has n minus one edges, whatever the graph has. The extra edges number m minus n minus one, the circuit rank. Cayley's formula, n to the n minus two, counts spanning trees of complete graphs. Other graphs need the Matrix-Tree Theorem. Here's something to think about. Suppose a connected graph has exactly one spanning tree. What must be true of the graph itself, and why? Think about what happens to the count as soon as the graph contains even one cycle.

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Spanning Trees and Their Properties

What is a spanning tree, and how is it different from a spanning forest?
A spanning tree of a connected graph G is a subgraph that contains every vertex of G, uses only edges of G, and is itself connected and acyclic. If G is disconnected, the analogous structure is a spanning forest, with one spanning tree for each connected component. A graph can have many different spanning trees.
Why is a graph connected if and only if it has a spanning tree?
A graph is connected exactly when it has a spanning tree. If a spanning tree exists, any two vertices are joined by a path in it, and that path lies in G. Conversely, in a connected graph, repeatedly delete an edge from a cycle. This keeps the graph connected, and the process ends because the edge count is finite. It stops only when no cycle remains, leaving a spanning tree.
How do you compute the circuit rank of a graph?
The circuit rank of a connected graph with m edges and n vertices is m-(n-1)=m-n+1. Every spanning tree has n-1 edges, so this counts the redundant edges, each of which closes a cycle. For example, a graph with 5 vertices and 5 edges has circuit rank 5-5+1=1. Any tree has circuit rank 0.
How many spanning trees does a complete graph have, and when does the formula not apply?
Cayley's formula says the complete graph K_n has exactly n^{n-2} spanning trees, so K_4 has 4^2=16. It applies only to complete graphs. A graph with five vertices and nine edges, which is K_5 missing one edge, does not have 5^3=125 spanning trees. Its count is 75. For non-complete graphs, count directly or use the Matrix-Tree Theorem.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →