Graph kernel Created 2026-10-14 Updated 2026-10-18
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 , one self-loop at each, and a single joining edge . Suppressing 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 . Thus forming a graph kernel compresses degree-two chains rather than deleting everything outside graph cycles.