Lecture Notes for Graph Theory

A First Look at Graph Theory

Authors

John Clark and Derek Allan Holton

Course

IT208 Artificial Intelligence

Contents Overview

  1. An Introduction to Graphs1.1 Introduction1.2 Graph as Models1.3 More Definitions1.4 Vertex Degrees1.5 Subgraphs1.6 Paths and Cycles1.7 Matrix Representation of a Graph

  2. Trees and Connectivity2.1 Definitions and Simple Properties2.2 Bridges2.3 Spanning Trees2.4 Cut Vertices and Connectivity

  3. Euler Tours and Hamiltonian Cycles3.1 Euler Tours3.2 Hamiltonian Graphs3.3 Plane and Planar Graphs3.4 Euler’s Formula

Introduction to Graph Theory

1.1 Introduction

Definition: Graph theory is a specialized branch of mathematics focused on the study and analysis of graphs, which are structures used to model pairwise relations between objects. It is essential for visualizing and solving problems through diagrams.Applications: The principles of graph theory are widely employed in numerous fields, including operations research, physics, social sciences, chemistry, biology, and computer science, particularly in the study of networks.Objective: This course aims to introduce the fundamental concepts of graph theory, enriched with examples and elementary results that offer a comprehensive understanding of the subject.

1.2 Graph as Models

Definition 1.1.1: GraphA graph G is represented as (V(G), E(G)), where:

  • V(G): Vertex set, a non-empty collection of elements known as vertices or nodes, which can represent things such as locations or entities in a network.

  • E(G): Edge set, containing unordered pairs of vertices called end vertices of an edge. Edges can represent connections or relationships, and can include loops where edges connect the same vertex.

1.3 More Definitions

Examples of basic Graph Elements:

  • Parallel Edges: Multiple edges that connect the same pair of vertices.

  • Isolated Vertex: A vertex with no edges incident to it, hence not connected to any other vertices.

  • Adjacency: A relationship between two vertices connected directly by an edge.

  • Neighborhood Set: Denoted as N(v), it includes all vertices that are neighbors of vertex v.

  • Simple Graph: A graph that contains no loops or parallel edges—it has distinct edges among different pairs of vertices.

  • Graph Isomorphism: A scenario where two graphs can be considered equivalent by relabeling their vertices, indicating a one-to-one correspondence.

  • Complete Graph (K_n): A specific type of simple graph where every pair of distinct vertices is directly connected by an edge.

  • Bipartite Graph: A unique structure in which vertices can be divided into two distinct sets such that edges only connect vertices from different sets, helpful in representing relationships like job assignments or social networks.

1.4 Vertex Degrees

Definition of Vertex Degree (1.4.1):A vertex’s degree, denoted as d(v), counts the number of edges incident to it, where edges connected by loops count as double.Theorem: Euler's Theorem states that the sum of the degrees of all vertices in a graph equals twice the number of edges in the graph, expressed mathematically as n = 2m, where n is the sum of all vertex degrees and m is the number of edges.

1.5 Subgraphs

Definitions:

  • Subgraph H: A graph derived from G if its vertices and edges are subsets of G.

  • Proper Subgraph: A subgraph H is termed proper if H is not equal to G.

  • Vertex Deleted Subgraph: An operation that entails removing one vertex from the graph along with all edges incident to that vertex.

  • Edge Deleted Subgraph: Involves the removal of an edge from G but preserves all vertices.

1.6 Paths and Cycles

Definitions:

  • Walk: A route that consists of alternating vertices and edges.

  • Path: A specific type of walk where all vertices are distinct.

  • Cycle: A closed trail in a graph where the starting and ending vertices are the same but every other vertex is distinct.Theorem: Theorem 1.6.1 establishes that if two vertices are connected by a walk, then there exists a path connecting those vertices.

1.7 Matrix Representation of a Graph

In more advanced studies, graphs can also be represented using various matrix forms, such as adjacency matrices or incidence matrices, which provide a method to study the properties and relationships within graphs mathematically.

Trees and Connectivity

2.1 Definitions and Simple Properties

Trees are a specific type of graph that is acyclic, meaning they do not contain cycles, and are connected, meaning there is a path between any two vertices. Key properties include that a tree with n vertices has exactly n-1 edges.

2.2 Bridges

A bridge in a graph is an edge which, when removed, increases the number of connected components of the graph. Identifying bridges is crucial in understanding graph connectivity and stability.

2.3 Spanning Trees

A spanning tree of a graph G is a subgraph that is a tree and includes all the vertices of G, providing a minimal connection framework.

2.4 Cut Vertices and Connectivity

Cut vertices or articulation points are critical vertices which, when removed, increase the number of connected components in the graph, thus crucial for maintaining connectivity.

Euler Tours and Hamiltonian Cycles

3.1 Euler Tours

Euler tours are defined as a trail in a graph that visits every edge exactly once and returns to the starting vertex. The existence of such a tour depends on specific conditions related to the degrees of the vertices in the graph.

3.2 Hamiltonian Graphs

Hamiltonian paths visit every vertex exactly once. A Hamiltonian cycle begins and ends at the same vertex, creating a closed loop of distinct vertices. The challenge in detecting the presence of these paths and cycles in graphs is a well-studied problem in computer science.

3.3 Plane and Planar Graphs

Graphs that can be drawn on a plane without any edges crossing are termed planar graphs. This property has significant implications in geography, circuit design, and network routing.

3.4 Euler’s Formula

Euler’s formula relates the number of vertices (V), edges (E), and faces (F) in a connected planar graph as V - E + F = 2, providing a fundamental relationship in graph theory that is essential for planar graph representation analysis.

Applications and Illustrative Examples

Throughout this exploration of graph theory, various illustrative examples will be provided to elucidate these concepts, including practical applications in social networks, communication networks, transportation routing, and resource allocation. The lecture's aim is to foster an understanding of how graph theory can model real-world scenarios and solve complex problems effectively.