24.1.1. Definition of a Graph

A graph is a collection of two sets: a set of vertices (or nodes) and a set of edges. The set of vertices is denoted by the set $V$, where $V \neq \emptyset$. This means that the vertex set is a non-empty set. The edges are denoted by the set $E$, which consists of edges of the form $(v_i, v_j)$, where both $v_i, v_j \in V$. The edge set can be empty, i.e., $E = \emptyset$.

A graph consists of two main components: vertices and edges. Vertices are the nodes or points in the graph, and there has to be at least one vertex. The edges are the connections between these vertices, which can express relationships or pathways. Importantly, the edge set can be empty, meaning that the graph can exist with just vertices and no connections. This is foundational in graph theory, helping to define what constitutes a graph.

Imagine a social network: each person is a vertex, and the friendships or connections between them are the edges. You can have individuals (vertices) without any friendships (edges), but you cannot have friendships without at least one person!

There are two types of graphs: directed graphs and undirected graphs. In directed graphs, edges have directions associated with them, meaning there is a starting point and an ending point for each edge. Each edge is represented as an ordered pair, indicating that the order matters. In contrast, undirected graphs have edges without direction, which means an edge between two vertices $v_1$ and $v_2$ is considered the same as an edge from $v_2$ to $v_1$.

The distinction between directed and undirected graphs is crucial in graph theory. In directed graphs, the edges represent one-way roads; for instance, a road from city A to city B is not the same as a road from city B to city A. Meanwhile, undirected graphs represent two-way roads where a connection is mutual; if one person is friends with another, that relationship goes both ways.

Think of directed graphs like a website's links, where clicking a link takes you from one page to another in a specific way, indicating direction. Undirected graphs can be likened to a roundabout where traffic can flow in either direction; the connection is mutual and does not indicate a preferential path.

A simple graph is defined as a graph that has no self-loops and has at most one edge between any two nodes. For example, if there are two vertices $v_1$ and $v_3$, multiple edges connecting them means it is not a simple graph. In a directed graph example, if there are two directional edges from $v_1$ to $v_3$ and from $v_3$ to $v_1$, it can still qualify as a directed simple graph.

Simple graphs maintain clarity by having one unique connection between any pair of vertices and avoiding self-loops, which can complicate the representation of relationships. This characteristic helps in analyzing the graph without the confusion that multiple connections can cause.

Imagine a group project where everyone has a unique contribution without redundancy. If each team member represents a vertex, then a simple graph would show a straightforward line of communication (or relationships) without over-representing connections. For instance, if two members were connected by multiple discussion points, it would confuse who contributed what.

In undirected graphs, a pair of vertices $(u, v)$ are called adjacent or neighbors of each other if the edge $(u, v) \in E$. If a vertex has an incident edge, we say that the edge is incident with the vertices at its endpoints. The degree of a vertex $v$ is defined as the number of edges incident with it, factoring in self-loops as contributing double to its degree.

Understanding the terminology surrounding undirected graphs is key to analyzing them. Adjacent vertices are those that are directly connected by an edge, and the concept of degrees allows us to understand the connectivity of each vertex. Self-loops add an interesting twist where they count twice towards the vertex's degree, indicating a strong self-connection.

Visualize a community where every neighbor (adjacent vertex) you have represents a direct connection (edge) to them. If you lived on a cul-de-sac (with a loop), the number of times you interact with your direct neighbors is like counting connections multiple times, especially if you spend extra time with one particular neighbor (self-loop)!

--