Splitting off

Undirected graphs

Let G=(V+s,E) be an undirected graph where the degree of s is at least two. If u and v are neighbours of s, splitting off su and sv means deleting the two edges su and sv, and adding an edge uv to the graph. Note that if there are several parallel edges between s and u, then we delete only one of them, except when u=v.

If the degree of s is even, a complete splitting off at s means that we arrange the edges incident to s into pairs [math](su_1,sv_1),\dots,(su_k,sv_k)[/math], and we split off all of these pairs. Thus s becomes isolated and the new edges are [math]\{u_1v_1,\dots,u_kv_k\}[/math].

The reverse operation of a complete splitting off is called pinching: if G=(V,E) is an undirected graph and [math]\{u_1v_1,\dots,u_kv_k\}\subseteq E[/math], then pinching this set of edges means deleting them from the graph, adding a new node s, and adding edges [math]su_1,sv_1,\dots,su_k,sv_k[/math].

Directed graphs

Splitting off in directed graphs can be defined similarly. Let D=(V+s,A) be a directed graph. If us and sv are in A, splitting off us and sv means deleting these two arcs and adding an arc uv to the digraph. If the in-degree of s equals its out-degree, a complete splitting off at s is a sequence of splitting of operations at s after which s becomes isolated. The reverse operation is called pinching in digraphs too.