### Unit 8: Graphs and Trees

Graphs serve innumerable functions: they can represent communications systems, chart knowledge, and even solve problems. In this unit, we will acquaint ourselves with special kinds of mathematical graphs while discussing graph concepts from degree and vertex to isomorphism. We will then turn to trees, which comprise a special category of graphs, as they serve special purposes and have different structures. We will conclude with a study of tree and graph properties. Trees and graphs have application to artificial intelligence, scheduling problems, and transportation systems.

**Completing this unit should take you approximately 8 hours.**

Upon successful completion of this unit, you will be able to:

- construct and identify different types of graphs and trees;
- determine properties of graphs and trees, including degree, diameter, connectivity, tours, and cycles;
- prove graph isomorphism; and
- use graphs and trees to model and solve problems.

### 8.1: Introduction to Graph Theory

Read this article.

A graph is simple if there is at most one arc associated with a pair of vertices. A graph that is not simple is called a multigraph.

Think of graphs as models for representing the elements and relations of a problem that we wish to solve.

### 8.2: The Concept of Graph Degrees

Think about a graph and imagine some properties that a graph might have that are characteristic of a graph - essential properties, i.e. not superficial properties like the labels for the nodes. Think some more about how we might define quantitative properties, i.e. those properties that take on numeric values. The following subunits present some thinking on these matters.

### 8.2.1: Total Degrees of a Graph

Read Definition 3 on pages GT-4 to GT-5.

### 8.2.2: The Handshake Theorem

Read the article for a description of the handshaking lemma and the degree sum formula.

### 8.3: Isomorphism of Graphs

Read Section 1.6. Isomorphism of two graphs is a formal way of saying that two graphs are essentially the same. Essentially the same means that they are the same with respect to specified properties that characterize a graph.

Let G and H be two graphs. To show G and H are isomorphic, construct a bijection from the vertices of G to the vertices of H that preserves adjacency. The adjacency matrix, defined in section 4, is helpful in supping the construction of an isomorphic mapping.

G and H are not isomorphic if:

- there is no bijection from the vertices of G to H;
- there is no bijection that preserves adjacency of vertices; and
- G and H have different properties, e.g. vertices have different degrees.

- there is no bijection from the vertices of G to H;

### 8.4: Trees

Read Section 5 on trees on pages 15 - 18. Please note that the definition of tree or the properties of trees (Theorem 8) can be used to determine if a graph is a tree.

Read this article for a discussion of types of trees.

### Unit 8 Assessment

Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment