What is a tree in graph theory?

An undirected graph that is connected and acyclic. Equivalently, every pair of distinct vertices has exactly one simple path between them.

An undirected acyclic graph. Its connected components are trees, so it is a disjoint union of trees.

How are vertices and edges related in a finite tree?

A finite tree with $V$ vertices has $V-1$ edges.

How can the number of components in a forest be calculated?

For a finite forest, the component count is $V-E$, where $V$ is its number of vertices and $E$ its number of edges.

What distinguishes a leaf from a branch vertex?

A leaf has degree one; a branch vertex has degree at least three.

Discrete mathematicsLesson 2 of 4 in the course Graph theory

Tree Structure, Rooting, Properties, and Counting in Graph Theory

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

This lesson introduces trees as fundamental structures in graph theory. We will connect several equivalent ways to recognize a tree and distinguish trees from forests.

A tree is an undirected graph in which every pair of distinct vertices is connected by exactly one path. Equivalently, a tree is connected and acyclic: there is a path between every pair of vertices, and there are no cycles.

All flashcards

What is a tree in graph theory?: An undirected graph that is connected and acyclic. Equivalently, every pair of distinct vertices has exactly one simple path between them.
What is a forest?: An undirected acyclic graph. Its connected components are trees, so it is a disjoint union of trees.
How are vertices and edges related in a finite tree?: A finite tree with $V$ vertices has $V-1$ edges.
How can the number of components in a forest be calculated?: For a finite forest, the component count is $V-E$ , where $V$ is its number of vertices and $E$ its number of edges.
What distinguishes a leaf from a branch vertex?: A leaf has degree one; a branch vertex has degree at least three.

Quiz questions

What two properties define an undirected tree?Answer: It is connected and acyclic.
What is a spanning tree of a connected graph?Answer: A tree subgraph that contains every vertex.
What makes a directed acyclic graph a polytree?Answer: Its underlying undirected graph is a tree.
What condition defines a binary tree?Answer: Each vertex has at most two children.
How many trees are there on a fixed set of $n$ labeled vertices, according to Cayley's formula?Answer: $n^{n-2}$

Based on the Wikipedia article Tree (graph theory), licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Discrete mathematics lessons

Discrete mathematicsBinary Relations: Operations, Properties, Functions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsPigeonhole Principle: Counting, Collisions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsDe Morgan's Laws in Logic, Set Theory, and Boolean Algebra5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsEulerian Routes: Criteria, Construction, and Extensions5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsNumber Theory: Integer Structure, Methods, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsBinomial Coefficients: Expansion, Counting, and Identities5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Discrete mathematics