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


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 books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.