CS 111 - Discrete Mathematics A
Fall 2023
Shoghakat Stepanyan November 21, 2023 1 / 11
Forest
Definition
A cycle in a graph is a closed walk of length at least three in which
no intermediate vertex is repeated.
Shoghakat Stepanyan November 21, 2023 2 / 11
Forest
Definition
A cycle in a graph is a closed walk of length at least three in which
no intermediate vertex is repeated.
Definition
A graph, which does not contain cycles, is called an acyclic graph
or a forest.
Shoghakat Stepanyan November 21, 2023 2 / 11
Forest
Definition
A cycle in a graph is a closed walk of length at least three in which
no intermediate vertex is repeated.
Definition
A graph, which does not contain cycles, is called an acyclic graph
or a forest.
Example:
Shoghakat Stepanyan November 21, 2023 2 / 11
Tree
Definition
A connected, acyclic graph is called a tree.
Shoghakat Stepanyan November 21, 2023 3 / 11
Tree
Definition
A connected, acyclic graph is called a tree.
Example: Each component of a forest is a tree.
Shoghakat Stepanyan November 21, 2023 3 / 11
Tree - Equivalent Conditions
Theorem 1
A graph is a tree if and only if between any two vertices there is a
unique path.
Shoghakat Stepanyan November 21, 2023 4 / 11
Tree - Equivalent Conditions
Theorem 1
A graph is a tree if and only if between any two vertices there is a
unique path.
Theorem 2
Let G be a connected graph. Then G is a tree if and only if every
edge of G is a cut edge.
Shoghakat Stepanyan November 21, 2023 4 / 11
Leaf
Definition
A vertex of degree 1 in a graph is called a leaf.
Shoghakat Stepanyan November 21, 2023 5 / 11
Leaf
Definition
A vertex of degree 1 in a graph is called a leaf.
Example:
Shoghakat Stepanyan November 21, 2023 5 / 11
Leaves
Theorem 3
Every tree with at least two vertices has a leaf.
Shoghakat Stepanyan November 21, 2023 6 / 11
Leaves
Theorem 3
Every tree with at least two vertices has a leaf.
Proposition
Let T be a tree and let v be a leaf of T . Then T − v is a tree.
Shoghakat Stepanyan November 21, 2023 6 / 11
Leaves
Theorem 3
Every tree with at least two vertices has a leaf.
Proposition
Let T be a tree and let v be a leaf of T . Then T − v is a tree.
Remark
The converse of the Proposition is also true.
Shoghakat Stepanyan November 21, 2023 6 / 11
The Number of Edges in a Tree
Theorem 4
Let T be a tree with n ≥ 1 vertices. Then T has n − 1 edges.
Shoghakat Stepanyan November 21, 2023 7 / 11
The Number of Edges in a Tree
Theorem 4
Let T be a tree with n ≥ 1 vertices. Then T has n − 1 edges.
Example
Find the total degree of a tree with 15 vertices.
Shoghakat Stepanyan November 21, 2023 7 / 11
The Number of Edges in a Tree
Theorem 4
Let T be a tree with n ≥ 1 vertices. Then T has n − 1 edges.
Example
Find the total degree of a tree with 15 vertices.
P |V (T )| = 15. Hence,
Solution: Let T be a tree with
|E (T )| = 15 − 1 = 14 ⇒ v ∈V d(v ) = 2|E | = 2 · 14 = 28.
Shoghakat Stepanyan November 21, 2023 7 / 11
Spanning Trees
Definition
Let G be a graph. A spanning tree of G is a spanning subgraph of
G that is a tree.
Shoghakat Stepanyan November 21, 2023 8 / 11
Spanning Trees
Definition
Let G be a graph. A spanning tree of G is a spanning subgraph of
G that is a tree.
Example:
Shoghakat Stepanyan November 21, 2023 8 / 11
Spanning Trees
Theorem 5
A graph has a spanning tree if and only if it is connected.
Shoghakat Stepanyan November 21, 2023 9 / 11
Spanning Trees
Theorem 5
A graph has a spanning tree if and only if it is connected.
Theorem 6
Let G be a connected graph on n ≥ 1 vertices. Then G is a tree if
and only if G has exactly n − 1 edges.
Shoghakat Stepanyan November 21, 2023 9 / 11
Equivalent Conditions
Corollary
Let G be a graph. The following statements are equivalent:
Shoghakat Stepanyan November 21, 2023 10 / 11
Equivalent Conditions
Corollary
Let G be a graph. The following statements are equivalent:
1. G is a tree.
Shoghakat Stepanyan November 21, 2023 10 / 11
Equivalent Conditions
Corollary
Let G be a graph. The following statements are equivalent:
1. G is a tree.
2. G is connected and acyclic.
Shoghakat Stepanyan November 21, 2023 10 / 11
Equivalent Conditions
Corollary
Let G be a graph. The following statements are equivalent:
1. G is a tree.
2. G is connected and acyclic.
3. Between any two vertices of G there is a unique path.
Shoghakat Stepanyan November 21, 2023 10 / 11
Equivalent Conditions
Corollary
Let G be a graph. The following statements are equivalent:
1. G is a tree.
2. G is connected and acyclic.
3. Between any two vertices of G there is a unique path.
4. G is connected and every edge of G is a cut edge.
Shoghakat Stepanyan November 21, 2023 10 / 11
Equivalent Conditions
Corollary
Let G be a graph. The following statements are equivalent:
1. G is a tree.
2. G is connected and acyclic.
3. Between any two vertices of G there is a unique path.
4. G is connected and every edge of G is a cut edge.
5. G is connected and |E (G )| = |V (G )| − 1.
Shoghakat Stepanyan November 21, 2023 10 / 11
Home reading and Exercises
Reading: E.R. Scheinerman – Chapter 9, Section 50.
Exercises: 50.1-50.19.
K. Rosen
Exercises: – 11.1 – 1,2, 14-17, 31, 32.
Shoghakat Stepanyan November 21, 2023 11 / 11
