Definitions

Subset Notation

The concept of choosing $k$ -element subsets from a set $X$ is captured by the notation $(\binom{X}{k})$ . Here, $X$ can be any collection of distinct objects, and $k$ is a non-negative integer. We define

(\binom{X}{k}) := {A \subset X : | A | = k}

which collects all subsets of $X$ containing exactly $k$ elements.

This notation generalizes the familiar binomial coefficient when $X$ is finite; for $| X | = n$ , we recover the number of $k$ -element subsets, often written as $(\binom{n}{k})$ . In this abstract form, we focus on the subsets themselves rather than just their count.

Understanding $(\binom{X}{k})$ is essential for defining the edges of an undirected graph, since edges are unordered pairs of vertices. The set $(\binom{V}{2})$ will serve as the universe from which graph edges are drawn.

$Example$
Let $X = {1, 2, 3}$ and $k = 2$ . Then

(\binom{X}{2}) = {{1, 2}, {1, 3}, {2, 3}} .

$Metaphor$
Choosing $k$ friends for a team from your class of $| X |$ students is like forming every possible group of size $k$ — that’s exactly what $(\binom{X}{k})$ represents.

Graph Definition (Undirected)

An undirected graph $G$ is specified by a pair $(V, E)$ , where $V$ is an arbitrary set of $vertices$ and

E = E (G) \subset (\binom{V}{2})

is a collection of $edges$ , each edge being a two-element subset of $V$ .

Vertices serve as the fundamental units or points in the graph, and edges connect pairs of vertices without any inherent direction. By restricting $E$ to subsets of size 2, we ensure that loops and multiple edges are excluded in this simple graph model.

undirected graph.png|300

This framework provides a versatile way to model relationships in networks, social connections, or any system of pairwise interactions.

$Example$
A triangle graph has $V = {a, b, c}$ and

E = {{a, b}, {b, c}, {a, c}} .

triangle graph.png

$Metaphor$
Think of vertices as towns and edges as bidirectional roads connecting them.

Adjacency and Incidence

Two vertices $u, v \in V$ are called $adjacent$ if the edge $u v$ belongs to $E$ . In symbolic form,

u and v are adjacent ⟺ u v \in E .

An edge $e$ is said to be $incident$ to its two endpoints $u$ and $v$ . Incidence describes the relationship between an edge and each vertex it connects.

Adjacency and Incidence Example.png

Understanding adjacency and incidence is crucial for exploring paths, connectivity, and other graph-theoretic properties.

$Example$
In the triangle graph above, $a$ and $b$ are adjacent since $a b \in E$ , and the edge $a b$ is incident to both $a$ and $b$ .

$Metaphor$
If vertices are people, adjacency is like two people shaking hands; the handshake (edge) is incident to both participants.

Order and Size

The $order$ of a graph $G$ , denoted $n (G)$ , is the number of vertices:

n (G) = | V | .

The $size$ of $G$ , denoted $m (G)$ , is the number of edges:

m (G) = | E | .

Order and size quantify the basic scale of a graph and are fundamental parameters in graph analysis, impacting complexity and connectivity.

$Example$
A triangle graph has order $n (G) = 3$ and size $m (G) = 3$ .

$Metaphor$
In a road network, order is the number of cities, and size is the number of roads.

Degree of a Vertex

The $vertex$ in a graph represents an entity or node within the structure. Each $vertex$ can be connected to other vertices via $edges$ .

The $degree$ of a vertex $v$ , denoted $d_{G} (v)$ or $d (v)$ , counts how many $edges$ are incident to $v$ . It quantifies the immediate connectivity of $v$ within the graph.

When a specific graph $G$ is clear from context, we often write $d (v)$ instead of $d_{G} (v)$ for brevity. This notation streamlines discussions when only one graph is under consideration.

graph have degrees (3, 2, 2, 1).png
Figure 1. Degrees of vertices in a graph

Understanding $degree$ is fundamental for analyzing graphs, as it appears in many algorithms for traversals, connectivity checks, and network analysis.

$Example$
In a triangle graph with vertices ${A, B, C}$ and edges ${A B, B C, C A}$ , each vertex has $degree$ $2$ .

$Metaphor$
The $degree$ of a $vertex$ is like counting how many roads enter an intersection in a road network.

Special Vertices: Isolated Vertex and Leaf

A $vertex$ whose $degree$ is $0$ is called an $isolated vertex$ . It has no $edges$ connecting it to any other $vertex$ .

An $isolated vertex$ stands completely alone in the graph, making it a candidate for special handling in algorithms that ignore unreachable components.

A $vertex$ with $degree$ $1$ is known as a $leaf$ . It connects to exactly one other $vertex$ via a single $edge$ .

Degree of Vertex of a Graph. Isolated Vertex and Leaf.png
Figure 2. Isolated vertex (e) and leaf (c).

$Example$
In a graph with vertices ${A, B, C, D}$ and edges ${A B, A C}$ , $D$ is an $isolated vertex$ , while $B$ and $C$ are both $leaves$ .

$Metaphor$
An $isolated vertex$ is like a remote cabin with no roads leading to it, and a $leaf$ is like a dead-end street connecting to only one other road.

Neighborhood of a Vertex

The $neighborhood$ of a $vertex$ $v$ is the set of all vertices directly connected to $v$ by an $edge$ .

Formally, $N (v) = {u : u v \in E (G)}$ , where $E (G)$ is the set of all $edges$ in graph $G$ . It captures the immediate adjacency of $v$ .

Analyzing $N (v)$ is crucial for exploring local properties of graphs, such as local clustering, degree-based centrality, and BFS expansions.

Illustration of the vertex neighbouring.png|500
Figure 3. Neighborhood of a vertex.

$Example$
In the same graph ${A, B, C, D}$ with edges ${A B, A C}$ , the $neighborhood$ of $A$ is ${B, C}$ .

$Metaphor$
The $neighborhood$ of a $vertex$ is like a person’s friend list in a social network, listing everyone they are directly connected to.

Conclusion

This excerpt establishes the foundational definitions of simple undirected graphs.

We introduced the notation $(\binom{X}{k})$ for $k$ -element subsets, defined a graph $G = (V, E)$ with vertices and edges, and clarified the notions of adjacency and incidence.

We saw how the order $n (G)$ and size $m (G)$ measure a graph’s scale, setting the stage for deeper exploration of graph-theoretic concepts.

We defined the $degree$ of a $vertex$ as the number of $edges$ incident to it, using the notation $d_{G} (v)$ or $d (v)$ to quantify connectivity.

Special cases arise when the $degree$ is $0$ , yielding an $isolated vertex$ , or $1$ , yielding a $leaf$ , each requiring distinct considerations in graph algorithms.

The $neighborhood$ $N (v)$ collects all vertices adjacent to $v$ , providing a foundation for local analysis, traversal techniques, and measures of influence within networks.