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 O’Reilly online learning.

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