## Chapter 9

## Graph Theory

#### Learning Objectives

On completing this chapter, you should be able to:

define the notions of a graph, directed graph and a simple graph

define and calculate the degree of a vertex in a graph

define the concept of a connected graph

define the notions of walks and paths connecting two vertices of a given graph

identify connected graphs

identify the connected components of a graph, which is not connected

define the notion of bipartite graphs

define the notion of a tree

prove simple results on connected graphs

prove simple results on trees

define the notion of an Euler graph

prove the characterization of an Euler graph

##### 9.1 INTRODUCTION AND MOTIVATION

#### Example 9.1

Graphs can be used to show the inter-connectivity among ...

Get *Discrete Mathematics and Combinatorics* now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.