Path-cycle matching
= Path-cycle matching
A <path-cycle matching> in a finite <simple graph> is a collection of mutually <vertex-disjoint paths> and <cycles in a graph>. Its used <edges> form a <subgraph> with every <degree of a vertex> at most two. Conversely, every finite <connected component of a graph> with maximum <degree> at most two is a <graph path>, a <cycle in a graph>, or an <isolated vertex>; following successive <edges> proves this classification. Discarding unused <isolated vertices> therefore converts any such <subgraph> into a <path-cycle matching> without changing its <edge> count. On a <bipartite graph>, maximizing the used <edges> is exactly <bipartite b-matching> with every $b_v=2$.