The computational strength of matchings in countable graphs

Stephen Flood, Matthew Jura, Oscar Levin +1

In a 1977 paper, Steffens identified an elegant criterion for determining when a countable graph has a perfect matching. In this paper, we will investigate the proof-theoretic stre…