A combinatorial structure consisting of a set of vertices (nodes) and a set of edges (pairs or ordered pairs of vertices) used to represent discrete relationships, connectivity, and interactions.

Principle

Adjacency encodes binary relations: the presence, direction and weight of edges capture the architecture of connections; graph-theoretic concepts (paths, components, cycles, cuts) formalize connectivity properties independent of embedding.

Demonstration

A social network where vertices represent people and weighted edges represent communication frequency: components reveal disconnected communities, shortest-path algorithms identify minimum-hop introductions, and centrality measures highlight influential nodes.

Misapplication

Interpreting a graph as a geometric object with metric properties based solely on node positions without using edge data, or treating multigraphs as simple graphs and thereby losing multiplicity information that affects flow or capacity calculations.

Consequence

Correct graph modeling yields algorithms for routing, clustering, matching and flow; spectral properties of graph matrices (adjacency, Laplacian) enable partitioning, diffusion modeling and stability analysis.

Reversal

Replacing discrete edges by continuous connections (a manifold or metric continuum) inverts the discrete relational model into a continuous domain where combinatorial algorithms no longer apply directly.

Boundary

Covers simple, directed, weighted, and multigraphs but excludes hypergraphs (edges connecting arbitrary subsets without pairwise reduction), simplicial complexes with higher-order faces, and purely geometric point clouds unless edges are defined.

Semantic Tension

Tension between 'graph' and 'network': graph emphasizes combinatorial structure, network often implies application context plus possible dynamics or metrics; tension also with adjacency matrix (algebraic representation) and with hypergraph (higher-order relations).

Synthesis

A graph is the discrete abstraction of pairwise connectivity: a minimal data structure (vertices plus edges) that admits combinatorial, algebraic and algorithmic analysis to model and solve problems about relationships and flow.