Discrete Mathematics and Combinatorics

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 ...