Graph Theory Introduction

What is Graph Theory?

Graph theory: Study of graphs (networks of connections)

Graph: Collection of vertices (nodes) connected by edges (links)

NOT the xy-coordinate graphs from algebra!

Applications:

• Social networks
• Computer networks
• Transportation routes
• Molecular structures
• Games and puzzles

Basic Terminology

Vertex (node): Point or location

Edge: Connection between two vertices

Adjacent vertices: Connected by an edge

Degree of vertex: Number of edges connected to it

Loop: Edge connecting vertex to itself

Multiple edges: More than one edge between same vertices

Example: Simple Graph

Vertices: A, B, C, D

Edges: AB, AC, BC, BD, CD

Degrees:

• deg(A) = 2 (connected to B and C)
• deg(B) = 3 (connected to A, C, D)
• deg(C) = 3 (connected to A, B, D)
• deg(D) = 2 (connected to B and C)

Types of Graphs

Simple graph: No loops or multiple edges

Multigraph: Can have multiple edges between same vertices

Directed graph (digraph): Edges have direction (arrows)

Weighted graph: Edges have values (distances, costs)

Complete graph: Every vertex connected to every other

Connected graph: Path exists between any two vertices

Example: Complete Graph K₄

4 vertices, every pair connected

Edges: AB, AC, AD, BC, BD, CD (6 edges total)

Each vertex has degree 3

Formula for complete graph Kₙ: n(n-1)/2 edges

Handshaking Lemma

Sum of all degrees = 2 × (number of edges)

Why? Each edge connects two vertices, so counted twice

Example: Verify Handshaking Lemma

Graph with degrees: 2, 3, 3, 2

Sum of degrees: 2 + 3 + 3 + 2 = 10

Number of edges: 5

Check: 2 × 5 = 10 ✓

Important consequence: Sum of degrees is always even!

Paths and Circuits

Path: Sequence of vertices connected by edges

Circuit (cycle): Path that starts and ends at same vertex

Simple path: No repeated vertices

Simple circuit: No repeated vertices except first/last

Length of path: Number of edges

Example: Paths and Circuits

Graph: A-B-C-D with edges AB, BC, CD, DA

Path from A to C: A → B → C (length 2)

Circuit: A → B → C → D → A (length 4)

Not a simple path: A → B → C → B (B repeated)

Euler Paths and Circuits

Euler path: Path using every edge exactly once

Euler circuit: Circuit using every edge exactly once

Named after mathematician Leonhard Euler

Famous problem: Seven Bridges of Königsberg

Euler's Theorem

Euler circuit exists if and only if:

• Graph is connected
• Every vertex has even degree

Euler path (not circuit) exists if and only if:

• Graph is connected
• Exactly two vertices have odd degree

Example 1: Check for Euler Circuit

Graph degrees: 2, 4, 2, 4

All even? Yes ✓

Connected? Yes ✓

Euler circuit exists!

Example 2: Check for Euler Path

Graph degrees: 3, 2, 2, 3

How many odd degrees? 2 (exactly two)

Connected? Yes ✓

Euler path exists! (but not circuit)

Path starts at one odd-degree vertex, ends at the other

Example 3: Neither

Graph degrees: 3, 3, 3, 3

Four odd-degree vertices

No Euler path or circuit

Seven Bridges of Königsberg

Historical problem that started graph theory (1736)

Question: Can you walk through city crossing each bridge exactly once?

Euler's solution:

• Model as graph (land = vertices, bridges = edges)
• All four land masses have odd degree
• Therefore, impossible!

First application of graph theory

Hamilton Paths and Circuits

Hamilton path: Path visiting every vertex exactly once

Hamilton circuit: Circuit visiting every vertex exactly once

Different from Euler (vertices vs edges)

No simple test like Euler's theorem

Example: Hamilton Circuit

Square graph: A-B-C-D with edges AB, BC, CD, DA

Hamilton circuit: A → B → C → D → A ✓

Visits each vertex once, returns to start

Example: Hamilton Path

Line graph: A-B-C-D

Hamilton path: A → B → C → D ✓

No Hamilton circuit (can't return without repeating)

Traveling Salesman Problem

Famous problem in computer science

Goal: Find shortest Hamilton circuit in weighted graph

Visits every city exactly once, returns to start

Applications:

• Delivery routes
• Circuit board drilling
• DNA sequencing

Challenge: No efficient algorithm for large graphs (NP-hard)

Trees

Tree: Connected graph with no circuits

Properties:

• Exactly one path between any two vertices
• n vertices have n-1 edges
• Removing any edge disconnects graph

Spanning tree: Subgraph that's a tree including all vertices

Example: Tree

Vertices: A, B, C, D, E

Edges: AB, AC, BD, BE (4 edges)

5 vertices, 4 edges → n-1 ✓

No circuits ✓

Connected ✓

This is a tree

Binary Trees

Binary tree: Each vertex has at most 2 children

Root: Top vertex

Leaf: Vertex with no children

Applications:

• Family trees
• Decision trees
• Computer science data structures

Example: Binary Tree

      A (root)
     / \
    B   C
   / \
  D   E (leaves: D, E, C)

Planar Graphs

Planar graph: Can be drawn without edges crossing

Euler's formula for planar graphs:

V - E + F = 2

Where:

• V = vertices
• E = edges
• F = faces (regions including outer region)

Example: Euler's Formula

Square graph:

• V = 4 vertices
• E = 4 edges
• F = 2 faces (inside and outside)

Check: 4 - 4 + 2 = 2 ✓

Complete Graphs K₅ and K₃,₃

K₅: Complete graph with 5 vertices (all connected)

K₃,₃: Complete bipartite graph (3 vertices in each group, each connected to all in other group)

Important fact: K₅ and K₃,₃ are NOT planar

Cannot draw them without edges crossing

Kuratowski's theorem: Graph is planar if and only if it doesn't contain K₅ or K₃,₃ (or subdivision)

Coloring Graphs

Graph coloring: Assign colors to vertices so adjacent vertices have different colors

Chromatic number: Minimum colors needed

Four Color Theorem: Any planar graph can be colored with 4 colors

Example: Coloring

Triangle graph (3 vertices, all connected):

Need 3 colors (each vertex adjacent to other two)

Chromatic number = 3

Example:

• Vertex A: Red
• Vertex B: Blue
• Vertex C: Green

Applications: Social Networks

Vertices: People

Edges: Friendships or connections

Degree: Number of friends

Path length: Degrees of separation

"Six degrees of separation" theory

Example: Facebook Graph

Average degree: ~150 friends per person

Average path length: ~4.5 connections

Small world phenomenon

Applications: Computer Networks

Vertices: Computers or routers

Edges: Network connections

Weighted edges: Bandwidth or latency

Find shortest path: Dijkstra's algorithm

Network reliability: Multiple paths (redundancy)

Applications: Chemistry

Vertices: Atoms

Edges: Chemical bonds

Degree: Valence of atom

Graph isomorphism: Same molecular structure

Example: Methane (CH₄)

Vertices: C (carbon), H₁, H₂, H₃, H₄ (hydrogens)

Edges: C-H₁, C-H₂, C-H₃, C-H₄

Carbon has degree 4 (4 bonds)

Each hydrogen has degree 1

Bipartite Graphs

Bipartite: Vertices can be divided into two groups with edges only between groups

Test: Graph is bipartite if and only if it has no odd-length circuits

Applications:

• Matching problems
• Job assignments
• Course scheduling

Example: Bipartite Graph

Group 1: Students (A, B, C)

Group 2: Courses (X, Y, Z)

Edges: Which student can take which course

A-X, A-Y, B-Y, C-Z

Matching problem: Assign each student one course

Practice