Graph Theory

• A branch of Mathematics that deals with networks or graphs

• A graph is defined as an ordered pair where is the vertex set and is the edge set. Edges consist of pairs .

  When the context is clear, we abbreviate with , and . We also assume are finite

• Graphs abstract pairwise relations between objects.

• Graphs are recursive structures. Manipulating a graph gives a smaller graph.

• One miracle of Graph Theory is how the Matching Problem can be rephrased in many ways. (see The Matching Problem).

Topics §

• Graph Theory — Notation Guide

• Fundamental Constructs of Graph Theory

• Families of Graphs

  • Trails, Walks, Paths and Cycles
  • Trees
  • Infinite Graph
  • Directed Graph

• Operations on Graphs

• Graph Connectivity

• Graph Planarity

• Graph Coloring

• The Matching Problem

• Flow Network

• Graph Algorithms

• Graph Duality

• Quantities in Graph Theory

Links §

• Introduction To Graph Theory by Wilson
• Graph Theory With Applications by Bondy and Murty