Graph Basics

Overview

The World of Graphs

A graph is a mathematical structure that models pairwise relationships between objects. Graphs are everywhere: social networks (people connected by friendships), road maps (cities connected by highways), the internet (web pages connected by links), and molecular structures (atoms connected by bonds). Graph theory gives us the tools to analyze these networks.

Definition

Graph

A graph G = (V, E) consists of: • V = a set of vertices (also called nodes) • E = a set of edges, where each edge connects two vertices

An edge between vertices u and v is written {u, v} (undirected) or (u, v) (directed).

Definition

Graph Terminology

Adjacent: Two vertices connected by an edge. Incident: An edge is incident to its endpoints. Degree: The degree of vertex v, written deg(v), is the number of edges incident to v. Neighbor: Vertex u is a neighbor of v if {u, v} is an edge. Loop: An edge from a vertex to itself. Multiple edges: Two or more edges between the same pair of vertices. Simple graph: No loops or multiple edges.

Theorem

Handshaking Theorem

In any graph G = (V, E): ∑ deg(v) = 2|E| (summing over all v ∈ V)

Every edge contributes 2 to the total degree (one for each endpoint).

Corollary: The number of vertices with odd degree is always even.

Example

Handshaking Theorem Example

A graph has 5 vertices with degrees 2, 3, 3, 4, 2. How many edges?

Sum of degrees = 2 + 3 + 3 + 4 + 2 = 14. Number of edges = 14 / 2 = 7.

Definition

Types of Graphs

Complete graph Kₙ: Every pair of n vertices is connected. Has n(n-1)/2 edges. Bipartite graph: Vertices split into two groups; edges only between groups. Complete bipartite Kₘ,ₙ: Every vertex in one group connects to every vertex in the other. Has m × n edges. Directed graph (digraph): Edges have direction (arrows). Weighted graph: Each edge has a numerical weight.

Example

Special Graphs

K₃ (complete graph on 3 vertices): 3 vertices, each connected to the other two. Edges = 3(2)/2 = 3.

K₂,₃ (complete bipartite): One group has 2 vertices, the other has 3. Edges = 2 × 3 = 6.

Cycle C₅: 5 vertices in a ring, each connected to its two neighbors. Edges = 5, every vertex has degree 2.