Trees: Properties and Definitions | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Trees: Properties and Definitions

Discrete Mathematics · Chapter 11: Trees, Spanning Trees, and Minimum Cost NetworksSection 11.1 · lesson 71 of 879 min · free with a free account

← Adjacency Matrix and List RepresentationsNext lesson: Tree Traversal Methods →

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

Connected, with no way back to where you started.

  • Define trees and forests
  • Use root, leaf, parent, child, depth and height
  • Prove a tree on n vertices has n - 1 edges
  • Recognize trees in real hierarchies

Transcript

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

Trees, Spanning Trees, and Minimum Cost Networks

Trees: Properties and Definitions

Chapter eleven is about trees, the one shape a hierarchy is always allowed to have. This section defines a tree precisely, introduces the vocabulary of rooted trees, and proves the fact that makes trees so predictable. A tree on n vertices always has exactly n minus one edges.

The Opening Problem

Every Web Page Is a Tree

Every time a browser renders a web page, it turns the page's H T M L into a data structure called the Document Object Model, or DOM. The html element contains a head and a body. The head contains a title, and perhaps a meta tag. The body holds the visible content. Every element has exactly one parent, available in JavaScript as parent element, and any number of children. And tracing parents upward from any element always ends in the same place, the document root. Nothing in a well-formed page ever loops back on itself. A single root, every piece reachable by exactly one path, and no loops. That shape is a tree. Trees sit behind DOM parsing, file system directories, organizational charts, and the decision trees used in interpretable machine learning.

11.1.1

Connected, Acyclic, Nothing Extra

Recall that a graph is connected if every pair of vertices is joined by a path. And a cycle is a closed walk, of at least three edges, that repeats no vertex except its start. A tree is a simple graph that's both connected and acyclic, meaning it has no cycle. A forest is acyclic, but not necessarily connected. Every one of its components is a tree. Both requirements matter, and neither implies the other. Three graphs on the same five vertices show it. T r has edges one two, one three, three four and three five. It's connected, and it has no cycle, so it's a tree, with five vertices and four edges. Add the single edge two four, and you get G b. It's still connected, but now it has the cycle one, two, four, three, one. So it isn't a tree, even though it differs by just one edge. And F s has edges one two, two three and four five. It's acyclic, but vertex one can't reach vertex four. It's a forest of two trees, not a single tree.

11.1.2

Rooted-Tree Vocabulary

A tree becomes a rooted tree once one vertex is chosen as the root. Because a tree is connected and acyclic, there's exactly one path from the root to every other vertex. If some vertex had two different paths back to the root, following both would trace out a cycle. That uniqueness makes the vocabulary well defined. The depth of a vertex is the number of edges on its path from the root. So the root has depth zero. The second-to-last vertex on that path is the vertex's parent, and the vertex is its child. A vertex with no children is a leaf. A vertex with at least one child is an internal vertex. And the height of the tree is the greatest depth of any vertex. Equivalently, it's the length of the longest path from the root to a leaf.

Worked Example

Depths in a DOM Tree

Root the DOM tree at html. It has seven vertices and six edges. html has depth zero. head and body have depth one. title, meta and p have depth two. And text, reached by html, head, title, text, has depth three. The leaves, with no children, are meta, p and text. The internal vertices are html, head, body and title. The height is the greatest depth, which is three, reached only at text. Even though the other two leaves sit at depth two. So height measures the single longest root-to-leaf path, not the depth typical of most leaves.

11.1.3

Every Tree Has a Leaf

Every tree seen so far has one fewer edge than vertices. That's a theorem, and proving it needs one small fact first. The lemma says every finite tree with at least two vertices has a leaf, meaning a vertex of degree one. Take a longest path in the tree. One exists, because the tree is finite. Now look at the path's last vertex. It can't have a neighbor off the path. That neighbor would extend the path, and the path is already longest. And it can't be adjacent to any earlier vertex on the path, other than the one just before it. That would close a cycle, which a tree can't contain. So its only neighbor is the vertex just before it on the path. It's a leaf.

Theorem

n Vertices, Exactly n - 1 Edges

Now the theorem. Every tree with n vertices has exactly n minus one edges. The proof is by induction on n. With one vertex, there are no edges, and n minus one is zero. For the inductive step, take a tree with n vertices, where n is at least two. By the lemma, it has a leaf. Remove the leaf, and its single edge. What remains is still connected, since no path between the other vertices ever passed through the leaf. And it's still acyclic, since removing a vertex can't create a cycle. So it's a tree on n minus one vertices, and by the inductive hypothesis, it has n minus two edges. Restore the leaf's edge, and the total is n minus one. The converse is also true. A connected graph with n vertices and exactly n minus one edges must be a tree. Why? If it contained a cycle, deleting one cycle edge would keep it connected, with only n minus two edges. But a connected graph on n vertices needs at least n minus one. So there's no cycle.

Worked Example

A Check and a Non-Example

The DOM tree has seven vertices and six edges, matching n minus one. Remove the leaf text, and its edge, and six vertices with five edges remain. That's still n minus one, just as the inductive step says. But the count by itself doesn't guarantee a tree. Take H, with vertices P, Q, R and S, and edges P Q, Q R and R P. It's a triangle, plus an isolated vertex S. It has four vertices and three edges, exactly n minus one. Yet it's disconnected, since S reaches no one, and it has a cycle. Not a tree, despite the right number of edges.

11.1.4

Trees in Practice

The DOM is a rooted tree in the fully literal sense. The browser's own interface models parents and children exactly as defined here. A well-formed page with n nodes has exactly n minus one parent-child edges, since every node but the root has exactly one parent. File systems follow the same pattern. Every file or folder has exactly one parent directory, except the root. So n entries means n minus one containment edges. Decision trees share the skeleton for a different reason. Each internal vertex tests one feature, like whether a transaction is over five hundred dollars. Each branch is an outcome, and each leaf is a prediction. Whatever the vertices represent, the guarantee is the same. Connected, acyclic and rooted means n minus one edges, and exactly one path from the root to every vertex. The next section covers how to walk those paths systematically.

Takeaways

One Path to Everything

To summarize. A tree is a connected, acyclic graph. Drop either requirement, and you get something else entirely, a cyclic graph or a forest. Rooting a tree gives every vertex a unique path from the root. That's what defines parent, child and depth. And height is the single greatest depth. Every tree on n vertices has exactly n minus one edges, proved by removing leaves. Conversely, a connected graph with n minus one edges is a tree. But n minus one edges alone guarantees nothing, as the triangle plus an isolated vertex shows. Here's something to think about. A rooted binary tree has one hundred leaves. A classmate says every internal vertex splits into exactly two children, so there must be exactly ninety-nine internal vertices. What property is that reasoning silently assuming? And can you describe a small rooted tree, with more than one internal vertex, where leaves equals internal vertices plus one fails?

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 Trees: Properties and Definitions

What is a tree in graph theory, and how is it different from a forest?
A tree is a simple graph that is both connected and acyclic: every pair of vertices is joined by a path, and there is no cycle. A forest only has to be acyclic, so it may be disconnected. Each component of a forest is a tree. Dropping either requirement of a tree gives a different kind of graph.
How do you find the root, parent, child, leaf, depth, and height of a rooted tree?
Choose a root, then use the unique path from the root to each vertex. Depth is the number of edges on that path, so the root has depth 0. The vertex just before v on the path is its parent, and v is its child. A leaf has no children. Height is the greatest depth of any vertex, not the typical depth of the leaves.
How do you prove that a tree with n vertices has exactly n - 1 edges?
Use induction on n. For n=1 there are 0 edges, and n-1=0. For n\ge 2, every finite tree has a leaf, namely the end of a longest path. Removing that leaf and its one edge leaves a tree on n-1 vertices, which has n-2 edges by hypothesis. Adding the edge back gives n-1.
If a graph has n vertices and n - 1 edges, is it automatically a tree?
No. The edge count alone does not guarantee a tree. A triangle plus an isolated vertex has 4 vertices and 3 edges, yet it is disconnected and contains a cycle. A connected graph with n vertices and n-1 edges is a tree. An acyclic graph with n vertices and n-1 edges is also a tree.

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 →