Discrete Mathematics - Graph Theory

DMA 25/26 Week 4 - Aarbaz Alam, LSBU

Course References

• Chapters referenced: 1 & 2, Chapter 10, Sections 1 - 5.

Graph Theory

Definition of a Graph

• A graph $G(V, E)$ is defined as an algebraic structure consisting of:

  • Two sets:

  • Vertices/Nodes Set $(V)$:

    • Denoted as: $V = {v<em>1, v</em>2, v_3, \ldots}$ where $V$ is a non-empty set of vertices.

  • Edges/Links Set $(E)$:

    • Denoted as: $E = {e<em>1, e</em>2, e<em>3, \ldots}$ where edges connect pairs of vertices $v</em>i, v_j$.

Graph Representation

• Graphs can be represented visually through diagrams.

  • Example representation:

  • Vertices: $V = {v<em>1, v</em>2, v<em>3, v</em>4, v_5}$

  • Edges: $E = {e<em>1, e</em>2, e<em>3, e</em>4, e<em>5, e</em>6, e_7}$

  • Alternatively can be compactly noted as:

  • $V = v_i,$ where $1 \leq i \leq 5$

  • $E = e_j,$ where $1 \leq j \leq 7$

Graph as a Relation

• Definition of a relation:

  • Given sets:

  • $S = {a, b, c}$

  • The Cartesian product $S^2$ generates all possible ordered pairs:

  • $S^2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}$

  • A subset of this relation forms a graph $G(V,E)$ where:

  • $V = S$ and $E \subseteq S^2$

Graph Terminologies

Key Definitions

• Adjacency:

  • Two vertices are adjacent if they are endpoints of the same edge:

  • $\text{adj}(v<em>i, v</em>j) \rightarrow e_{i,j} \in E$

    • Example: $v<em>1$ & $v</em>2$, $v<em>2$ & $v</em>2$.

• Incidence:

  • An edge is incident to a vertex if it is one of its endpoints:

  • Example: $v<em>1$ & $e</em>4$, $v<em>2$ & $e</em>1$.

• Degree:

  • The degree of a vertex $v<em>i$, denoted as $ ext{deg}(vi)$, is the number of edges incident to it:

  • $\text{deg}(v<em>i) = |{v</em>j | \text{adj}(v<em>i, v</em>j)}|$.

    • Examples: $ ext{deg}(v1) = 3$, $ ext{deg}(v2) = 3$.

• Pendent Vertex/Leaf:

  • A vertex with degree = 1 (e.g., $v_5$).

• Isolated Vertex:

  • A vertex with degree = 0.

• Parallel Edges/Chords:

  • When a pair of adjacent vertices has multiple edges between them:

  • Example: $\ ext{Parallel Edges: } {e<em>4, e</em>5}$ is parallel between $v<em>1$ & $v</em>3$.

• Self Loop:

  • An edge with identical endpoints:

  • Example: $e<em>1 = e</em>{2,2}$.

Types of Graphs

Undirected Graph

• Graph where edges have no direction.

  • The connection between any two vertices is bidirectional:

  • $\text{Edge } (u, v) \equiv (v, u)$.

  • Example: Friendship networks, where if A is a friend of B, then B is also a friend of A.

  • Represented as: $G = (V, E)$ where $E$ is a set of unordered pairs.

Directed Graph (Digraph)

• Graphs where edges have a specific direction.

  • Connections are not bidirectional:

  • Edge $(u, v) \neq (v, u)$ - connection goes from $u$ to $v$ only.

  • Often depicted with arrows indicating direction.

  • Example: Following relationships on social platforms, e.g., Instagram follower graph.

  • Represented as: $G = (V, E)$ where $E$ is a set of ordered pairs.

Graph Types and Properties

Problem Example: Königsberg Bridge Problem

• Problem statement from the historical perspective:

  • There are 4 islands, labeled $A, B, C, D$, connected by 7 bridges.

• Objective:

  • Find a path that allows one to start from any of the islands, traverse all 7 bridges without repeating any, and return to the start point.

• Reference: Königsberg Bridge

Graph Applications in Real Life

Example 1: Google Maps

• Graph representation of different locations, roadways, and distances.

Example 2: London Tube

• The tube network can be represented as a graph where stations are vertices and the lines are the edges connecting these vertices.

Example 3: Facebook Graph API

• Demonstrates the social network as a graph using relationships:

  • Connections include:

  • friends, likes, follows, etc.

Example 4: Network Topologies in Computer Science

• Utilizing graphs to represent network topologies, routers, and connections in operating systems.

Graph Classifications

Finite & Infinite Graph

• A graph $G(V, E)$ is:

  • Finite Graph: If $V$ and $E$ are both finite sets.

  • Infinite Graph: If either vertex set or edge set is infinite.

Regular Graph

• A graph where all vertices have equal degree.

Null Graph

• A graph that has a finite vertex set but does not have any edges:

  • Example: $G(V, E)$ where $E = \emptyset$ and $V \neq \emptyset$.

Isomorphism in Graphs

Definition and Conditions

• Isomorphism:

  • Two graphs $G<em>1$ and $G</em>2$ are isomorphic ($G<em>1 \approx G</em>2$) if they have:

  • A one-to-one correspondence between their vertices, edges, and adjacencies.

• Necessary Conditions for Isomorphism:

  • Same number of vertices.

  • Same number of edges.

  • Identical sets of vertex degrees.

Testing for Isomorphism

1. Step 1: Evaluate:

   • Number of vertices:

     • $|V<em>1| = 5$ and $|V</em>2| = 5$.

   • Number of edges:

     • $E<em>1 = 6$ and $E</em>2 = 6$.

   • Degree sets:

     • $D<em>1 = {3, 2, 3, 3, 1}$ and $D</em>2 = {3, 2, 3, 3, 1}$.

2. Step 2: Test if $G<em>1 \approx G</em>2$.

Properties of Subgraphs

• Definition:

  • $G<em>1(V</em>1, E<em>1)$ is a subgraph of $G</em>2(V<em>2, E</em>2)$ written as $G<em>1 \subseteq G</em>2$ if:

  • $V<em>1 \subseteq V</em>2$ and $E<em>1 \subseteq E</em>2$.

• Properties:

  • Reflexive: Every graph is a subgraph of itself.

  • Antisymmetric: Subgraph relation is non-commutative except for isomorphic graphs.

  • Transitive: A subgraph of a subgraph is also a subgraph.

• Every vertex and edge in a graph is trivially considered a subgraph.

Walk, Path, and Circuit Definitions

Walk/Chain

• Definition: A finite alternating sequence of vertices and edges beginning and ending with vertices.

  • No edge appears more than once.

  • End points are called Terminal Vertices; others are Intermediate Vertices.

  • Closed Walk: If a vertex is revisited; Open Walk: otherwise.

Path

• Definition: An open walk where no redundant vertex exists.

Circuit

• Definition: A closed walk, where the terminals are identical.

  • Denoted as $C_n$ for a circuit of n vertices.

Graph Connectivity

Connected Graph

• A graph is connected if there is at least one path between every pair of vertices.

  • If not, the graph is considered disconnected.

  • Components: In a disconnected graph, each isolated connected graph is referred to as a component.

Eulerian Path and Circuit

Definitions

• Euler Line: A walk that traverses every edge exactly once; an open walk.

• Euler Circuit: A closed walk that visits every edge exactly once.

• Euler Graph: A graph containing at least one Euler line.

  • Arbitrarily Traceable Graph: A graph from which an Euler line can be drawn from any origin point.

Hamiltonian Path and Circuit

• Definition:

  • Hamiltonian Path: A walk visiting every vertex exactly once (open walk).

  • Hamiltonian Circuit: Returns to the starting vertex while visiting every vertex exactly once (closed walk).

Complete Graphs

• A complete graph (or mesh or clique) is defined by maximal connectivity:

  • Number of edges $= \frac{n(n-1)}{2}$ for n vertices.

  • Denoted as $K_n$.

Graph Colouring Problem

• Given a graph $G(V, E)$:

  • Each vertex is assigned a color such that no two adjacent vertices share the same color.

  • The minimum number of colors required is known as the Chromatic Number, denoted $\chi(G) \in \mathbb{N}$.

  • Key Observations:

  • $\chi(K_n) = n$

  • $\chi(C_n) = 2$ if n is even;

  • $\chi(C_n) = 3$ if n is odd (and greater than 1).

Theorems in Graph Theory

1. For a connected graph, the edge set is bounded by $E \in [n - 1, \frac{n(n-1)}{2}]$.

2. The sum of the degrees of all vertices is twice the number of edges:

   • $\sum d(v_i) \in V = 2|E|.$

3. The sum of degrees of all odd-degree vertices is an even number.

4. A disconnected graph can be partitioned into components.

5. There exists a path between pairs of odd-degree vertices in any graph.

6. A simple graph with n nodes and k components has a maximum of $\frac{(n-k)(n-k+1)}{2}$ edges.

7. All vertices of an Euler graph have even degrees.

8. In a complete graph with n vertices, there are $\frac{n-1}{2}$ edge-disjoint Hamiltonian circuits when n is odd and $\geq 3$.

Questions & Thank You

• Any questions regarding the lecture content?

• Thank you for your attention!