Graphs and Networks

Precise definition

A graph $G=(V,E)$ consists of a vertex set $V$ and an edge set $E$. In a simple undirected graph, each edge is an unordered pair of distinct vertices, with no loops or repeated edges. A path follows adjacent vertices without repeating vertices; a cycle is a closed path of positive length with no repeated internal vertex.

Notation and mathematical language

Vertices $u,v$ are adjacent when $\{u,v\}\in E$. The degree $\deg(v)$ counts incident edges. A graph is connected when every two vertices are joined by a path. Directed graphs use ordered pairs; weighted graphs attach costs or lengths, so definitions and algorithms must match the graph type.

Conceptual picture

A graph deliberately suppresses irrelevant geometry: vertices may be redrawn anywhere without changing adjacency. What matters is which objects are linked. Adjacency lists emphasize local neighbours; adjacency matrices support algebraic operations; a drawing supports visual reasoning but can hide crossings or suggest nonexistent edges.

Conditions and key results

For a finite undirected graph, the handshaking lemma states $\sum_{v\in V}\deg(v)=2|E|$, because every edge contributes two incidences. Consequently the number of odd-degree vertices is even. A path and a walk are not synonyms, and connectivity claims require all vertex pairs, not merely a large component.

A reliable strategy

1. Declare whether the network is directed, weighted, simple, or allows loops and parallel edges.
2. Translate the context into vertices and edges, then list adjacency before relying on a drawing.
3. Use degree sums, paths, components, or an appropriate traversal to answer the structural question.
4. Check the result against invariants such as the handshaking lemma and test isolated or boundary vertices.

Fully worked example

Interpretation and application

Graphs represent roads, communication links, social ties, task dependencies, and molecules. An edge can mean very different relationships; a social-network edge records association, not necessarily influence or causation. Weighted shortest paths require weights with a clear interpretation such as distance, time, or cost.

Common mistakes

Verification and reasonableness

• Recompute the degree sum from the edge list and confirm it equals twice the number of edges.
• Verify each claimed path edge-by-edge and each connectivity claim component-by-component.
• Redraw the graph or compare adjacency lists; structural conclusions should be unchanged.

Practice

1. A simple graph has degrees $3,3,2,2,2$. How many edges does it have?
2. Can a finite undirected graph have exactly three odd-degree vertices?
3. In the worked graph, what happens when $CD$ is removed?

Further deduction

An adjacency matrix $M$ for a simple graph has $M_{ij}=1$ exactly when vertices $i$ and $j$ are adjacent. It is symmetric for an undirected graph and has a zero diagonal when loops are forbidden. Matrix multiplication adds a deeper fact: $(M^k)_{ij}$ counts walks of length $k$ from $i$ to $j$. These are walks, not necessarily paths, because vertices may repeat. This distinction lets algebra answer reachability questions while preserving the graph-theoretic definitions.

Related topics

• Trees
• Algorithms
• Relations