Graphs and Basic Definitions

Graph theory forms the mathematical foundation for studying networks, relationships, and structures across computer science, operations research, and discrete mathematics. A graph provides an abstract model for representing pairwise relationships between objects.

DefinitionGraph

A graph $G = (V, E)$ consists of:

A finite set $V$ of vertices (or nodes)
A set $E \subseteq \{\{u,v\} : u,v \in V, u \neq v\}$ of edges

Each edge connects two distinct vertices. If edge $e = \{u,v\}$ , we say $u$ and $v$ are adjacent and that $e$ is incident to both $u$ and $v$ .

The number of vertices $|V| = n$ is the order of the graph, while $|E| = m$ is its size. For vertex $v \in V$ , the degree $\deg(v)$ counts the number of edges incident to $v$ . The neighborhood $N(v) = \{u \in V : \{u,v\} \in E\}$ consists of all vertices adjacent to $v$ .

DefinitionSpecial Graphs

Complete graph $K_n$ : Every pair of distinct vertices is adjacent ( $m = \binom{n}{2}$ )
Empty graph $\overline{K_n}$ : No edges ( $m = 0$ )
Path graph $P_n$ : Vertices $v_1, v_2, \ldots, v_n$ with edges $\{v_i, v_{i+1}\}$ for $i = 1, \ldots, n-1$
Cycle graph $C_n$ : Path $P_n$ with additional edge $\{v_n, v_1\}$ (requires $n \geq 3$ )
Bipartite graph: Vertex set partitions as $V = A \cup B$ where all edges connect vertices from $A$ to $B$

ExampleComplete Bipartite Graph

The complete bipartite graph $K_{3,3}$ has vertex sets $A = \{a_1, a_2, a_3\}$ and $B = \{b_1, b_2, b_3\}$ with all nine possible edges between $A$ and $B$ . This graph is non-planar and plays a crucial role in Kuratowski's theorem.

A subgraph $H = (V', E')$ of $G$ satisfies $V' \subseteq V$ and $E' \subseteq E$ . If $E'$ contains all edges from $E$ with both endpoints in $V'$ , then $H$ is an induced subgraph, denoted $G[V']$ .

Remark

The handshaking lemma states that $\sum_{v \in V} \deg(v) = 2m$ , since each edge contributes 2 to the total degree sum. This implies that every graph has an even number of odd-degree vertices.

Graph isomorphism captures structural equivalence: graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic (written $G_1 \cong G_2$ ) if there exists a bijection $\phi: V_1 \to V_2$ preserving adjacency. Understanding graph structure through invariants like degree sequences and symmetries is fundamental to graph theory.