Пусть дан [[Граф (математика)|граф]] ''G'' = (''V'',''E''), '''паросочетание''' ''M'' в ''G'' это множество попарно несмежных рёбер, то есть рёбер, не имеющих общих вершин.
'''''Максимальное'''''<nowiki/>''' паросочетание''' — это такое паросочетание ''M'' в графе ''G'', которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам паросочетания. Другими словами, паросочетание ''M'' графа ''G'' является максимальным, если любое ребро в ''G'' имеет непустое пересечение по крайней мере с одним ребром из ''M''. Ниже приведены примеры максимальных паросочетаний (красные рёбра) в трёх графах.
: [[Файл:Maximal-matching.svg]]
'''''Наибольшее'''''''' паросочетание''' (или максимальное по размеру паросочетание<ref>Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.</ref>)— это такое паросочетание, которое содержит максимальное количество рёбер.
