سوال ۱۰۵ کنکور ارشد ریاضی ۱۴۰۱

منظور از یک تطابق کامل در یک گراف $G$، زیرمجموعه‌ای مانند $M$ از یال‌های $G$ است به‌طوری‌که هر رأس به دقیقاً یک یال از $M$ متصل باشد. گراف زیر دارای چند تطابق کامل است؟

(شکل: یک نردبان با ۲ سطر و ۹ ستون از رأس‌ها — در مجموع ۱۸ رأس: رأس‌های بالا $u_1,\dots,u_9$، رأس‌های پایین $v_1,\dots,v_9$، یال‌های افقی $u_iu_{i+1}$ و $v_iv_{i+1}$، ۹ یال عمودی $u_iv_i$، و در هر یک از ۸ خانهٔ مربعی یک قطر از گوشهٔ پایین‑چپ به گوشهٔ بالا‑راست، یعنی یال‌های $v_iu_{i+1}$ برای $i=1,\dots,8$.)