10.1184/R1/6478631.v1 Alan Frieze Alan Frieze On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three Carnegie Mellon University 2012 Random Graphs Hamilton Cycles 2-Matching Algorithm Greedy Algorithm 2012-12-12 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/On_a_Greedy_2-Matching_Algorithm_and_Hamilton_Cycles_in_Random_Graphs_with_Minimum_Degree_at_Least_Three/6478631 <p>We describe and analyse a simple greedy algorithm 2greedy that finds a good 2-matching <em>M</em> in the random graph when . A 2-matching is a spanning subgraph of maximum degree two and <em>G</em> is drawn uniformly from graphs with vertex set , <em>cn</em> edges and minimum degree at least three. By good we mean that <em>M</em> has components. We then use this 2-matching to build a Hamilton cycle in time w.h.p.</p>