= Graph kernel
{title2=$K(G)$}
For a <connected graph> whose <2-core> contains a <vertex> of <degree of a vertex> at least three, suppress each maximal <graph path> with degree-two internal <vertices> to a single <edge>, allowing its two endpoints to coincide. Here suppression is the reverse of <graph subdivision>. The resulting <multigraph>, retaining <self-loops> and parallel <edges>, is its <graph kernel>. Each suppressed internal <vertex> removes one <vertex> and one <edge>, preserving <graph excess>; counting a <self-loop> twice toward <degree of a vertex>, every remaining <vertex> has <degree of a vertex> at least three. A purely cyclic <2-core> is a separate unicyclic case: it has no branching <vertex> to anchor this construction.
For the barbell in <bridges and connectivity in the 2-core>, the <graph kernel> has two <vertices> $c,d$, one <self-loop> at each, and a single joining <edge> $cd$. Suppressing $x,y$ contracts the joining <graph path> to that <bridge in a graph>; suppressing the two other <vertices> on each triangle turns the triangle into a <self-loop>. The <graph excess> stays $9-8=3-2=1$. Thus forming a <graph kernel> compresses degree-two chains rather than deleting everything outside <graph cycles>.
Back to article page
