= Graph subdivision
{title2=$TH$}
A <graph subdivision> $TH$ replaces each <edge> $uv$ of a <simple graph> $H$ by a <graph path> of at least one <edge> joining its original endpoints. The original <vertices> are <branch vertices of a graph subdivision>. The replacement <graph paths> have pairwise disjoint interiors, contain no <branch vertices of a graph subdivision> internally, and together make up the entire new <graph>. Leaving an <edge> unchanged is allowed.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>[§1.7, printed p. 18: subdivision, branch vertices and subdividing vertices]{ref}
For an explicit example, take $H$ with <vertex set> $\{A,B,C,D\}$ and <edges> $AB,BC,CA,AD$: a <triangle in a graph> with one attached <leaf of a graph>. Replace its <edges> by the following <branch paths of a graph subdivision>:
$$
P_{AB}=(A,x,B),\qquad P_{BC}=(B,y,z,C),\qquad P_{CA}=(C,A),\qquad P_{AD}=(A,D).
$$
The resulting <graph subdivision> $S$ has <vertex set> $\{A,B,C,D,x,y,z\}$ and <edges> $Ax,xB,By,yz,zC,CA,AD$. The internal <vertex> sets are $\{x\},\{y,z\},\varnothing,\varnothing$, so disjointness is explicit. The <degrees of vertices> of $A,B,C,D$ remain $3,2,2,1$, respectively; the three new internal <vertices> each have <degree of a vertex> two.
\Image[/graph-subdivision-triangle-pendant-edge-paths.png]
{title=A <graph subdivision> of a <triangle in a graph> with an attached <leaf of a graph>: colours track the four <branch paths of a graph subdivision>}
Adding $m$ internal <vertices> to a finite <graph> increases both its <vertex> count and its <edge> count by $m$. Here $m=3$, so four <vertices> and four <edges> become seven of each; the <graph excess> is unchanged. Each replacement <graph path> remains a route between the same junctions. Thus <graph subdivision> preserves whether a <graph> is a <planar graph>: insert intermediate <vertices> along a crossing-free drawing, or trace each replacement <graph path> as one <edge> to recover a drawing of the original <graph>. Travel times or capacities are separate modelling choices and are not determined by this adjacency construction.
Back to article page
