Graph subdivision ($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.^[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.

A branch vertex of a graph subdivision is a retained original vertex in a specified graph subdivision. Its degree of a vertex in that graph subdivision equals its original degree of a vertex. It need not have degree of a vertex at least three: $B,C,D$ in the example are also branch vertices of a graph subdivision. When the target itself has vertices of degree of a vertex two, adjacency alone need not identify which vertices were original; the specified target mapping supplies that distinction.

A branch path of a graph subdivision is the replacement graph path for one original edge. Its endpoints are the corresponding branch vertices of a graph subdivision; its internal vertices have degree of a vertex two within the graph subdivision.

A $T{K}_r$ is a subdivision of the complete graph $K_r$. Its original complete-graph vertices are branch vertices and its replaced edges are branch paths.