Graph
Definition
Graph G: ordered pair (V, E). V = set of vertices, E = set of edges. Edges connect pairs of vertices.
Notation
Vertices: V(G). Edges: E(G). Order: |V|. Size: |E|.
Types of edges
Undirected edge: unordered pair {u,v}. Directed edge (arc): ordered pair (u,v).
Vertex (Node)
Definition
Vertex: fundamental unit, element of V. Represents objects or points.
Labels and degrees
Vertices may have labels or weights. Degree relates to number of incident edges.
Isolated and pendant vertices
Isolated vertex: degree zero. Pendant vertex: degree one.
Edge (Arc)
Definition
Edge: connection between two vertices. In undirected graphs, unordered pair; in directed, ordered pair.
Loops and multiple edges
Loop: edge connecting vertex to itself. Multiple edges: more than one edge between same vertices.
Edge notation
Edge e between u and v: e = {u,v} (undirected), e = (u,v) (directed).
Degree of a Vertex
Degree (undirected graphs)
Degree deg(v): number of edges incident to v. Loop counts twice.
In-degree and Out-degree (directed graphs)
In-degree: edges directed into vertex. Out-degree: edges directed out.
Degree sum formula
Sum of degrees equals twice number of edges: ∑deg(v) = 2|E|.
Path and Walk
Walk
Walk: sequence of vertices and edges where consecutive vertices connected by an edge. Vertices and edges may repeat.
Path
Path: walk with no repeated vertices (and hence no repeated edges).
Length of path
Number of edges in the path.
Cycle and Circuit
Cycle
Path starting and ending at same vertex, with no repeated edges or vertices except start/end.
Circuit
Closed walk with no repeated edges. May have repeated vertices.
Simple cycle
Cycle with no repeated vertices other than start/end.
Connectedness
Connected graph
Undirected graph where path exists between every pair of vertices.
Components
Maximal connected subgraphs. Graph partitioned into components.
Strongly connected (directed graphs)
For every pair (u,v), path from u to v and v to u.
Adjacency and Incidence
Adjacency
Vertices u and v adjacent if edge connects them.
Incidence
Edge e incident to vertices u and v if e connects u and v.
Adjacency matrix
Matrix A where A[i][j] = 1 if vertices i and j adjacent, else 0.
Subgraph
Definition
Graph H = (V_H, E_H) where V_H ⊆ V(G), E_H ⊆ E(G), edges in E_H connect vertices in V_H.
Induced subgraph
Subgraph formed by subset of vertices and all edges between them in G.
Spanning subgraph
Subgraph containing all vertices of G.
Types of Graphs
Simple graph
No loops or multiple edges.
Multigraph
Allows multiple edges and loops.
Directed graph (digraph)
Edges have direction; ordered pairs.
Graph Isomorphism
Definition
Graphs G and H are isomorphic if bijection f: V(G) → V(H) preserves adjacency.
Properties preserved
Degree sequences, connectedness, cycles, subgraphs.
Applications
Graph matching, chemical compound comparison, network analysis.
Special Structures
Complete graph (K_n)
Every pair of distinct vertices connected by edge. |E| = n(n-1)/2.
Bipartite graph
Vertices partitioned into two sets with edges only between sets.
Tree
Connected acyclic graph. |E| = |V| - 1.
Forest
Disjoint union of trees.
Planar graph
Can be drawn on plane without edge crossings.
References
- West, D. B., Introduction to Graph Theory, Prentice Hall, 2nd ed., 2001, pp. 1-500.
- Diestel, R., Graph Theory, Springer-Verlag, 5th ed., 2017, pp. 1-350.
- Bollobás, B., Modern Graph Theory, Springer, 1998, pp. 1-400.
- Chartrand, G., Lesniak, L., Graphs & Digraphs, CRC Press, 5th ed., 2010, pp. 1-520.
- Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, Elsevier, 1976, pp. 1-400.
Key Formulas and Tables
Degree Sum Formula
∑_{v ∈ V} deg(v) = 2|E|Complete Graph Edges
|E(K_n)| = n(n - 1)/2| Graph Type | Characteristics | Example |
|---|---|---|
| Simple Graph | No loops, no multiple edges | Social network without repeated connections |
| Multigraph | Allows loops and multiple edges | Transport network with multiple routes |
| Directed Graph | Edges have direction | Webpage link structure |
| Term | Description | Notation |
|---|---|---|
| Vertex | Element of vertex set | v ∈ V |
| Edge | Connection between vertices | e = {u,v} or (u,v) |
| Degree | Number of incident edges | deg(v) |
| Path | Sequence of distinct vertices connected by edges | P = v_1 ... v_k |
| Cycle | Closed path with start = end vertex | C = v_1 ... v_k v_1 |
Introduction
Graph theory studies structures composed of vertices and edges. Terminology is fundamental for understanding properties, algorithms, and applications in computer science, networking, biology, and more.
"A graph is a mathematical abstraction that captures relationships between objects, forming the backbone of discrete mathematics." -- Reinhard Diestel