Graphs & Networks

Graph

A collection of vertices connected by edges; used to model pairwise relationships.

Vertex (Node)

A point or location in a graph.

Edge (Arc)

A line connecting two vertices, representing a relationship.

Loop

An edge that connects a vertex to itself.

Multiple Edges

Two or more edges connecting the same pair of vertices.

Degree of a Vertex

The number of edges connected to a vertex (loops count as two).

Adjacent Vertices

Vertices directly connected by an edge.

Simple Graph

A graph with no loops or multiple edges.

Connected Graph

A graph where there is a path between every pair of vertices.

Disconnected Graph

A graph with at least one pair of vertices not connected by a path.

Complete Graph (Kₙ)

A graph where every pair of distinct vertices is connected by a unique edge.

Subgraph

A graph formed from a subset of vertices and edges of another graph.

Complement of a Graph

A graph with all edges between non-adjacent vertices of the original graph.

Weighted Graph

A graph where each edge has a numerical value (e.g., cost or distance).

Directed Graph (Digraph)

A graph where edges have direction, shown by arrows.

Undirected Graph

A graph where edges have no direction.

Path

A sequence of distinct vertices connected by edges.

Walk

A sequence of vertices connected by edges; vertices and edges may repeat.

Trail

A walk with no repeated edges.

Circuit

A trail that starts and ends at the same vertex.

Cycle

A circuit with no repeated vertices except the first/last.

Eulerian Trail

A trail that uses every edge exactly once.

Eulerian Circuit

A closed Eulerian trail—uses every edge once and starts/ends at the same vertex.

Eulerian Graph

A graph with an Eulerian circuit; all vertices have even degree.

Semi-Eulerian Graph

A graph with an Eulerian trail but not a circuit; exactly two vertices have odd degree.

Hamiltonian Path

A path that visits every vertex exactly once.

Hamiltonian Cycle

A Hamiltonian path that starts and ends at the same vertex.

Planar Graph

A graph that can be drawn without any edges crossing.

Face (Region)

An area bounded by edges in a planar graph (including the outer region).

Bridge

An edge whose removal increases the number of disconnected parts.

Tree

A connected graph with no cycles.

Spanning Tree

A subgraph that includes all vertices and is a tree.

Minimum Spanning Tree (MST)

A spanning tree with the smallest possible total edge weight.

Kruskal’s Algorithm

Builds an MST by adding the smallest edges one by one, avoiding cycles.

Prim’s Algorithm

Builds an MST by starting at a vertex and adding the smallest edge to a new vertex.

Network

A graph with weighted edges, modeling systems like roads or communication.