 Graph subdivision

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.^[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: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.

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.