شبه تطابق در گراف $G(V,E)$، مجموعه $P$ از $\left [ \frac{|V|}{2} \right ]$ مسیر مجزای یالی در $G$ است که حداقل $|V|-1$ راس از رئوس $V$ انتهاهای این مسیرها باشند.

ثابت کنید هر گراف همبند $G$ یک شبه تطابق دارد.

• سوال بعد
• سوال قبل