24.1.2. Types of Graphs

A graph is a collection of two sets, a set of vertices (nodes) and a set of edges. The set of vertices, denoted by the set $V$, is a non-empty set, and the edges are denoted by the set $E$, which can be of the form (v_i, v_j) where $v_i, v_j \in V$. The edge set could be empty, but the vertex set cannot be empty.

A graph consists of vertices and edges. Vertices are the points (or nodes) in the graph, and edges are the connections (or lines) between these points. For a graph to exist, it must have at least one vertex; otherwise, it cannot form any connections. An empty edge set means there are no connections between the vertices, but the vertices themselves must still exist in the graph.

Think of a graph like a group of friends (vertices) and the friendships (edges) that connect them. Even if some friends are not connected to anyone else (no edges), they still exist in the friend group.

There are two main types of graphs: directed and undirected. A directed graph has edges with directions, represented as ordered pairs, meaning the direction from one vertex to another matters. In contrast, an undirected graph has edges without direction, meaning the connection is the same regardless of the direction.

In directed graphs, edges have a specific start and end point, making (v_1, v_2) different from (v_2, v_1). For undirected graphs, an edge between two vertices does not have a direction, so (v_1, v_2) is the same as (v_2, v_1). This distinction affects how we analyze the relationships in graph theory.

Imagine sending a letter (directed) to a friend; the letter goes from you (the sender) to your friend (the receiver). Now consider a handshake (undirected); the handshake happens mutually, and it doesn’t matter who initiated it as both parties are equally involved.

A simple graph is one that has no self-loops and has at most one edge between any two nodes. For example, if there are two vertices and more than one edge between them, it cannot be classified as a simple graph.

In a simple graph, rules limit connectivity to prevent complexities like loops (where a vertex connects to itself) and multiple connections between the same vertices. This clarification helps maintain clarity in how graphs are structured and analyzed, making it easier to study their properties.

Think of a simple graph like a social network where each person (vertex) can only connect with another person (vertex) in one way (edge). You can't have someone being friends with the same person in multiple ways (no multiple friendships) or being friends with themselves (no self-loops).

In an undirected graph, a pair of vertices, $u$ and $v$, are adjacent or neighbors if there is an edge between them. The degree of a vertex is the number of edges incident on that vertex. Self-loops contribute twice to the degree.

Adjacent vertices are directly connected by an edge. The degree of a vertex indicates its level of connectivity; a higher degree means more connections. The inclusion of self-loops in the degree count means that if a vertex connects to itself, it effectively has two 'connections'.

Consider vertices as your friends at a party. If you talk to two friends directly, your degree is 2. If you talk to yourself by looking in a mirror (self-loop), it's like having an extra connection, raising your degree to 3.

In an undirected graph with $m$ edges, the sum of the degrees of all vertices is equal to twice the number of edges. This relationship helps reaffirm the interconnected nature of vertices in a graph.

The Handshaking Theorem explains that each edge contributes 1 to the degree of each of its endpoints. Therefore, when counting degrees, you essentially count each edge twice; once for each endpoint. This theorem is fundamental in understanding graph properties.

Imagine a gathering where everyone shakes hands. Each handshake is counted twice: once for the person initiating the shake and once for the person receiving it. Hence, if you count all handshakes, you will find the total connections relate directly back to the number of handshakes made.

There are special forms of graphs, including complete graphs, cycle graphs, wheel graphs, n-cubes, and bipartite graphs. Each of these graphs has unique features that distinguish them from general graphs.

Special types of graphs have defined structures that serve particular purposes in graph theory. For instance, a complete graph has exactly one edge between each pair of vertices, while a cycle graph connects in a circular path. Understanding these helps in applying graph theory to real-world problems.

Picture a sports league. A complete graph represents every team playing against every other team exactly once. A cycle graph might represent a round-robin tournament where each team plays another in a circular order. These structures allow for strategic planning based on relationships within the league.

--