A greedy algorithm for finding a large 2-matching on a random cubic graph

Deepak Bal, Patrick Bennett, Tom Bohman, Alan Frieze

Research output: Contribution to journalArticle


A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U is the number of edges in U and this is at least n-k(U) where n is the number of vertices of G and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching U with k(U)=Θ(n1/5).

Original languageEnglish
Pages (from-to)449-481
Number of pages33
JournalJournal of Graph Theory
Issue number3
Publication statusPublished - Jul 2018



  • 2-matching
  • greedy algorithm
  • random cubic graph

Cite this