Graph theory is a branch of mathematics that studies relationships between objects. The objects, often called vertices or nodes, are connected by edges. Here's an intuitive explanation:

Imagine you have a group of friends, and you want to represent how they know each other. Each friend is a point, or vertex, in our graph. If two friends are friends with each other, you draw a line between them, creating an edge.

Vertices: Represent individuals or entities (like cities, computers, or even abstract concepts).

Edges: Represent connections or relationships between the entities.

Graphs can be used to model a wide range of real-world situations:

1. Social Networks: Each person is a vertex, and friendships are edges.

2. Transportation Networks: Cities are vertices, and roads or flight paths are edges.

3. Web Pages: Web pages are vertices, and hyperlinks are edges.

4. Circuit Design: Components are vertices, and connections are edges.

There are different types of graphs, such as directed and undirected graphs:

• Undirected Graphs: Edges have no direction; the relationship is mutual (like friendships).

• Directed Graphs (Digraphs): Edges have a direction; the relationship may not be mutual (like following on social media).

Let's explore some more intuitive examples to deepen your understanding of graph theory:

1. Family Trees:

   • Vertices: Individuals (family members).
   • Edges: Parental relationships connecting parents to their children.
   • Applications: Analyzing relationships, finding common ancestors, understanding generational connections.

2. Board Games:

   • Vertices: Different positions on the board.
   • Edges: Legal moves or connections between positions.
   • Applications: Analyzing possible moves, finding winning strategies.

3. Friendship Chains:

   • Vertices: People.
   • Edges: Connections formed by friendships.
   • Applications: Understanding friend circles, identifying key connectors.

4. Library Book Arrangement:

   • Vertices: Books.
   • Edges: Relationships between books on the same topic.
   • Applications: Organizing books based on related content.

5. Food Web in Ecology:

   • Vertices: Species in an ecosystem.
   • Edges: Relationships like predation or mutualism.
   • Applications: Studying the interdependence of species in an ecosystem.

6. Puzzle Games:

   • Vertices: Different game states.
   • Edges: Legal moves or transitions between states.
   • Applications: Finding optimal solutions, understanding game dynamics.

7. City Navigation:

   • Vertices: Intersections or landmarks.
   • Edges: Roads or paths connecting them.
   • Applications: Finding the shortest route between locations, optimizing traffic flow.

8. Maze Solving:

   • Vertices: Different locations in the maze.
   • Edges: Open passages or walls.
   • Applications: Finding a path from the start to the exit.

9. Computer Network Topology:

   • Vertices: Computers or devices.
   • Edges: Communication links between devices.
   • Applications: Analyzing data flow, identifying potential bottlenecks.

10. Book Citations:

    • Vertices: Books or research papers.
    • Edges: Citations connecting works.
    • Applications: Understanding the influence of publications, tracking information flow.

These examples demonstrate how graph theory concepts can be applied to diverse situations, making it a versatile and powerful tool for modeling relationships and solving problems in a wide range of fields. Graph theory also explores concepts like paths (sequences of connected vertices), cycles (paths that form closed loops), and connectivity.

Here’s a simple example: Imagine a group of three friends, A, B, and C. A is friends with both B and C. In graph theory terms, you have three vertices (A, B, C) and two edges (A-B, A-C).

Graph theory provides tools to analyze and understand these structures. For example, you might want to find the shortest path between two people in a social network or determine the most efficient way to travel between two cities.

The beauty of graph theory lies in its simplicity and applicability to a vast array of scenarios, making it a powerful and versatile mathematical tool.

Graph Definition

A graph G is an ordered pair (V(G),E(G)) where V(G) is the set of vertices and E(G) is the set of edges. The incidence function ϕ_G associates each edge with an unordered pair of vertices. If e is an edge joining vertices u and v, then ϕ_G(e) = {u, v}.

Example 3

Let G₁ = (V₁,E₁) be a graph where V₁ = {A, B, C, D} E₁ = {e₁, e₂, e₃, e₄}

The incidence function ϕ_G1 is defined by: ϕ_G1(e₁) = AC,  ϕ_G1(e₂) = BD,  ϕ_G1(e₃) = AB,  ϕ_G1(e₄) = CD

Example 4

Let G₂ = (V₂,E₂) be another graph where V₂ = {X, Y, Z, W} E₂ = {f₁, f₂, f₃, f₄, f₅}

The incidence function ϕ_G2 is defined by: ϕ_G2(f₁) = YX,  ϕ_G2(f₂) = WY,  ϕ_G2(f₃) = WZ,  ϕ_G2(f₄) = ZY,  ϕ_G2(f₅) = XW

Graph of Friend Interests

Consider a social graph F where individuals are vertices, and edges connect friends who share common interests. Let’s denote the vertices as P for persons and the edges as I for shared interests.

Example 5

Let F₁ = (P₁,I₁) be a graph where P₁ = {Alice, Bob, Charlie, Diana} I₁ = {swimming, reading, cooking, hiking}

The friendships and shared interests are represented by edges: swimming : {Alice, Bob, Charlie, Diana} reading : {Alice, Charlie, Bob, Diana} cooking : {Alice, Diana, Bob, Charlie} hiking : {Alice, Bob, Charlie, Diana}

Example 6

Let F₂ = (P₂,I₂) be another graph where P₂ = {Eva, Frank, Grace, Henry} I₂ = {photography, traveling, painting, music}

The friendships and shared interests are represented by edges: photography : {Eva, Grace, Frank, Henry} traveling : {Eva, Henry, Frank, Grace} painting : {Eva, Frank, Grace, Henry} music : {Eva, Henry, Frank, Grace}

Visual Representation of Graphs

Graphs are versatile structures, and their visual representation allows for flexibility. The relative positions of vertices and the shapes of edges don’t carry inherent meaning. Different drawings may represent the same graph. Visualization merely aids in understanding the underlying structure.

Key Concepts in Graph Theory

Let’s dive into the fundamental concepts outlined in the text, exploring each in detail.

Incidence Relation and Vertex-Edge Relationships

The incidence relation in a graph defines how vertices and edges are connected. For instance, consider a social network graph where vertices represent individuals and edges denote friendships. The edge a joins vertices u and v.

Neighbours and Adjacent Vertices

Vertices that share a common edge are termed adjacent. In a geographical map graph where cities are vertices and roads are edges, cities B and C are adjacent if they share a road.

Loop, Link, and Parallel Edges

Graphs can have edges with distinct characteristics. A loop is an edge with identical ends, while a link has distinct ends. If two links share the same pair of ends, they are parallel edges. Consider a transportation network graph where b forms a loop, and c, d, e, and f are links. Edges e and g represent parallel connections.

Graph Notations and Types

Graph notations simplify representation. The letter G denotes a graph, and common symbols include V for vertices and E for edges. For instance, in a graph G with V = {A, B, C, D} and E = {a, b, c, d}, n = 4 and m = 4.

Focus on Finite Graphs

Graph theory primarily deals with finite graphs, where both the vertex set and edge set are finite. The null graph, with no vertices or edges, is introduced for mathematical convenience. A graph with only one vertex is trivial; all others are nontrivial.

Introduction

In graph theory, while drawings serve as a visual representation, they lack the computational efficiency required for storing and analyzing graphs. To bridge this gap, we turn to two powerful mathematical tools: the incidence matrix and the adjacency matrix. These matrices provide a structured, systematic, and computationally efficient way to represent and study graphs.

Incidence Matrix

Let G be a graph with vertex set V and edge set E. The incidence matrix of G, denoted as M_G, is a crucial representation capturing the relationships between vertices and edges.

Mathematical Definition

For a graph G with n vertices and m edges, the incidence matrix M_G is an n × m matrix where each entry m_ve is the number of times (0, 1, or 2) that vertex v and edge e are incident.

M_G := (m_ve)

Intuitive Explanation

Consider a graph where vertices represent individuals and edges represent connections. The incidence matrix M_G encodes how many times each person is incident to each connection, capturing the relational structure of the graph. Each row corresponds to a vertex, each column to an edge, and the entries indicate the incidence relationship.

Adjacency Matrix

The adjacency matrix, denoted as A_G, is a square matrix of order n × n, providing a compact representation of the connections between vertices.

Mathematical Definition

The entry a_ij in the adjacency matrix A_G is defined as follows:

$$a_{ij} = \begin{cases} 1 & \text{if there is an edge between vertices } i \text{ and } j \\ 0 & \text{otherwise} \end{cases}$$

Intuitive Explanation

In a graph, each vertex is either connected to another vertex or not. The adjacency matrix A_G encodes these connections, with a 1 indicating the presence of an edge and 0 indicating its absence.

Example

Let’s consider a simple graph G with vertices V = {A, B, C} and edges E = {e₁, e₂, e₃}.

$$M_G = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{bmatrix}$$

$$A_G = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}$$

In M_G, each row represents a vertex, each column an edge, and the entries indicate the incidence relationship. In A_G, each entry a_ij indicates whether there is an edge between vertices i and j.

Graph theory, a field rich with diverse structures, unveils a multitude of special families of graphs. Each family exhibits unique properties, offering insights into various aspects of connectivity and relationships. In this graduate-level exploration, we delve into the intricacies of complete graphs, cycle graphs, bipartite graphs, and more, providing intuitive explanations and accompanying adjacency matrices.

1. Complete Graphs (K_n)

A complete graph K_n is a fundamental family where every pair of distinct vertices is connected by an edge. Mathematically, this graph is denoted as K_n where n represents the number of vertices.

Intuitive Explanation

In a complete graph K_n, imagine n individuals attending a social gathering. Each person is directly connected to every other person, symbolizing that everyone knows everyone else.

Adjacency Matrix

For K_n, the adjacency matrix A_Kn is an n × n matrix where each entry a_ij is 1 if there is an edge between vertices i and j, and 0 otherwise.

$$A_{K_n} = \begin{bmatrix} 0 & 1 & \ldots & 1 \\ 1 & 0 & \ldots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \ldots & 0 \\ \end{bmatrix}$$

2. Cycle Graphs (C_n)

Cycle graphs C_n are characterized by a single closed loop, where each vertex is connected to exactly two others, forming a cycle. Mathematically, C_n represents a cycle of length n.

Intuitive Explanation

Think of a cycle graph C_n as a circular path with n points. Each point is connected to its two adjacent points, forming a closed loop like a bicycle wheel.

Adjacency Matrix

The adjacency matrix A_Cn for a cycle graph of length n is given by:

$$A_{C_n} = \begin{bmatrix} 0 & 1 & 0 & \ldots & 0 & 1 \\ 1 & 0 & 1 & \ldots & 0 & 0 \\ 0 & 1 & 0 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ldots & 1 & 0 \\ 1 & 0 & 0 & \ldots & 0 & 0 \\ \end{bmatrix}$$

3. Bipartite Graphs

Bipartite graphs divide their vertices into two disjoint sets, and edges only connect vertices from different sets.

Intuitive Explanation

Consider a bipartite graph as a gathering of individuals where everyone is either a student or a teacher. Edges represent the student-teacher relationships, connecting individuals from different categories.

Adjacency Matrix

For a bipartite graph, the adjacency matrix A_Bipartite is given by:

$$A_{\text{Bipartite}} = \begin{bmatrix} 0 & 1 & \ldots & 1 \\ 1 & 0 & \ldots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \ldots & 0 \\ \end{bmatrix}$$

Vertex Degrees

In the realm of graph theory, the degree of a vertex, denoted as d_G(v), reveals the number of edges connected to that vertex. Think of it as the "social popularity" of a vertex – how many edges it’s linked to. When we count these links, we count loops twice. Imagine each person in a network, where friendships (edges) are formed. The degree of an individual is the count of their friendships.

Isolated vertices, with a degree of zero, are like lone wolves in this social network, having no direct connections.

Now, let’s consider the overall popularity contest in the graph. The minimum degree (δ(G)) is the least popular person, the maximum degree (Δ(G)) is the most popular, and the average degree (d(G)) is the average popularity across all individuals.

Now, a cool identity links the total popularity (sum of degrees) with the total number of friendships (edges) in the network:

Theorem 1.1: For any graph G, Total Popularity = 2 × Total Friendships

Intuition: Imagine everyone in the network shaking hands. Each handshake involves two people, just like each edge involves two vertices. So, the total number of handshakes (degrees) is twice the number of friendships (edges).

Corollary 1.2: In any graph, the number of individuals with an odd number of friendships is always even.

Insight: Think about it like this – if someone has an odd number of friendships, every handshake contributes an odd number to the total. So, if the total is even, there must be an even number of odd contributions.

Now, let’s talk about special graphs. A graph is k-regular if everyone has exactly k friendships. It’s like a social club where everyone is equally popular. For instance, a complete graph, where everyone is friends with everyone, is (n−1)-regular. The complete bipartite graph, where everyone has friends in the other group, is k-regular.

For k = 0, 1, 2, these regular graphs are straightforward. But when k = 3, things get interesting. These graphs, known as cubic graphs, are like intricate social ecosystems. They play a significant role in graph theory, challenging us to explore the complexities of well-connected communities.

Vertex Degrees

In graph theory, let G be a graph with vertex set V and edge set E. The degree of a vertex v in G, denoted d_G(v), is defined as the function: d_G : V → ℕ₀ where ℕ₀ is the set of non-negative integers.

For a simple graph, d_G(v) represents the number of neighbors of v in G. An isolated vertex is one with d_G(v) = 0.

The minimum and maximum degrees of vertices in G are denoted by δ(G) and Δ(G) respectively: δ(G) = min_v ∈ Vd_G(v) Δ(G) = max_v ∈ Vd_G(v)

The average degree of G, denoted d(G), is defined as: $$d(G) = \frac{1}{|V|} \sum_{v \in V} d_G(v)$$

Now, consider a fundamental identity relating the degrees of the vertices and the number of edges in G: ∑_v ∈ Vd_G(v) = 2|E|

Corollary: In any graph, the number of vertices with odd degree is even, as ∑_v ∈ Vd_G(v) ≡ 0 (mod  2).

Regular Graphs

A graph G is said to be k-regular if d_G(v) = k for all v ∈ V. Mathematically, G is k-regular if: ∀v ∈ V, d_G(v) = k

For example, a complete graph on n vertices is (n−1)-regular.

Regular graphs with k = 0, 1, 2 have simple structures. However, k = 3 leads to complex structures, known as cubic graphs. These graphs, with every vertex having degree 3, play a crucial role in graph theory.