Graph (source code)
= Graph
{title2=$G=(V,E)$}
{wiki=Graph_(discrete_mathematics)}
\Image[/graph-adjacency-example.png]
{title=Two drawings of the same six-vertex <graph> and its <adjacency matrix>}
A graph describes objects, called <vertices>, and pairwise connections, called <edges>. Its <vertex set> $V$ tells us what the objects are; $E$ records their connections. The basic abstraction retains <graph adjacency> while discarding positions, angles and <Euclidean distances>: moving the dots in a drawing changes none of the <edges>. A crossing of two drawn lines is not an extra <vertex> unless explicitly designated as one. Even the labels can change: a <graph isomorphism> is a relabelling that preserves <graph adjacency> in both directions.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>{ref}
This makes <graphs> useful when the question concerns possible connections rather than physical shape. For example, model locations by <vertices> and direct links by <edges>; a <graph path> answers whether one location can reach another. Alternatively, let <vertices> be activities and <edges> represent conflicts: a <graph coloring> then assigns compatible time slots. These are mathematical models, so one must decide which pairwise relationship an <edge> means before applying <graph theory>.https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec11.pdf[MIT, Graphs and Coloring, Sections 1.3 and 2.1]{ref}
Our running <simple graph> has
$$
V=\{A,B,C,D,E,F\},\qquad E=\{AB,AC,BC,CD,DE,DF,EF\},
$$
where $AB$ abbreviates the <unordered pair> $\{A,B\}$. It consists of two <triangles in a graph>, $ABC$ and $DEF$, joined by $CD$. The two drawings above have identical <graph adjacency>, even though their apparent lengths differ. What counts is that $C$ and $D$ are adjacent, whereas $A$ and $F$ are not.
Route questions require precise vocabulary. A <walk> is a <sequence> of consecutive adjacent <vertices>, permitting repetitions; its length counts traversed <edges>. A <trail> is a <walk> that repeats no <edge>; a <graph path> repeats no <vertex>. For a <multigraph>, the <walk> must also specify which parallel <edge> each step uses. For instance, $A,B,A,C,D,F$ is a length-five <walk> but not a <trail>, since it uses $AB$ twice. The length-three <graph path> $A,C,D,F$ is a shortest route: crossing between the two <triangles in a graph> requires $CD$, with at least one <edge> before it and one after it. Thus $d(A,F)=3$ in <graph distance>, regardless of the drawing.https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec13.pdf[MIT, Connectivity and Trees, Section 1]{ref}
An <Eulerian trail> uses every <edge> exactly once, allowing repeated <vertices>; a <Hamiltonian path> visits every <vertex> exactly once, without needing every <edge>. Here $C,A,B,C,D,E,F,D$ is an <Eulerian trail> of length seven, whereas $A,B,C,D,E,F$ is a <Hamiltonian path> of length five. The first repeats $C,D$; the second omits $AC,DF$. Calling an <Eulerian trail> an "<Eulerian path>" must not be taken to impose our <graph path> convention.https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec13.pdf[MIT, Connectivity and Trees, Section 3]{ref}
The classic historical example is Euler's Königsberg bridge problem: represent the four land regions by <vertices> and the seven bridges by distinct <edges>, giving a <multigraph>. Their <degrees of vertices> are $3,3,3,5$. In a <trail> using every <edge>, arrivals and departures pair at every internal <vertex>, so at most the two endpoints can have odd <vertex degree>. Four odd <degrees of vertices> therefore rule out such a route. This early foundational example of <graph theory> needs neither bridge lengths nor a geographical map. Euler's paper is conventionally associated with 1736, the volume's nominal year; the Euler Archive records its writing in 1735 and publication in 1741.<Euler Archive, E53: Solutio problematis ad geometriam situs pertinentis>{ref}https://la.wikisource.org/wiki/Solutio_problematis_ad_geometriam_situs_pertinentis[Euler, original Latin text and edition details]{ref}
Back to article page
