VC ≤p MODEST

נניח שקיימת $S\subseteq V'$ עם $|S|\le k$ שהסרתה מותירה גרף צנוע. נבנה ממנה כיסוי של $G$.

נחליף עלים בקודקודיהם. נגדיר $U=\bigl(S\cap V\bigr)\ \cup\ \{\,v\ \mid\ \ell_v\in S\,\}.$ כלומר כל עלה ב-$S$ מוחלף בקודקוד המקורי שהוא תלוי בו. אז $U\subseteq V$ ו-$|U|\le|S|\le k$ (ההעתקה אינה מגדילה: כל איבר של $S$ תורם לכל היותר איבר אחד).

$U$ כיסוי של $G$. תהי $uv\in E$ ונניח בשלילה $u\notin U$ וגם $v\notin U$. מהגדרת $U$ נובע $u\notin S,\quad \ell_u\notin S,\quad v\notin S,\quad \ell_v\notin S .$ לכן כל ארבעת הקודקודים $u,\ell_u,v,\ell_v$ שרדו את ההסרה, וכן שרדו הקשתות $\{u,\ell_u\}$, $\{v,\ell_v\}$ ו-$\{u,v\}$ (קשת שורדת כאשר שני קצותיה שורדים). אז דרגת $u$ בגרף הנותר היא לפחות $2$ — השכנים $\ell_u$ ו-$v$ — בסתירה לכך שהגרף הנותר צנוע.

לכן $u\in U$ או $v\in U$, כלומר $U$ כיסוי בקודקודים של $G$ בגודל $\le k$, ומכאן $\langle G,k\rangle\in\mathrm{VC}$.