I need help formulating proof for a graph-theory problem: A graph $G = (V, E)$ is called quasi-factorizable if $G − u$ has a perfect matching for every vertex $u ∈ V$.
Show that $G$ is quasi-factorizable if and only if $q(G − S) ⩽ |S| − 1$, for every non-empty subset of vertices $S ⊆ V$. (q refers to the number of odd connected components)
I'm going to be honest graph theory is not my forte, so i tried to google for quasi-factorizable graphs to maybe get a clue, but i don't get even one reference to this type of graph. At this point i suppose my professor just made it up.
If anyone could give me ideas on how to go about writing a proof for this i'd be really greatful.
I understand that $q(G − S) ⩽ |S| − 1$ is derrives from Tutte's theorem (which would be like this $q(G − S) ⩽ |S|$). So basically, if i were to give proof from left to right, i'd have to prove $q(G − S) ⩽ |S| − 1$ from $q((G-e) − S) ⩽ |S|$ where e is any node from G. (because G is quasi-factorizable).
This essentially needs two ingredients: Tutte's theorem, and the observation that for any $u \in V, T \subset V\setminus \{u\},$ $$ (G-\{u\}) - T = G - (\{u\} \cup T),$$ which should be obvious (but make the argument if you haven't).
With this in hand, first if the graph is quasi-factorisable, then for any $u \in V,$ $G-\{u\}$ has a perfect matching, and so by Tutte's theorem we know that for any $u$, and any $T \subset V\setminus \{u\}$, $q((G-\{u\})-T) \le |T|.$ But any nonempty $S \subset V,$ for any $u \in S,$ it holds that $S = \{u\}\cup (S \setminus \{u\}),$ and so it follows that for any $S$, $$q(G-S) = q( (G-\{u\}) - (S\setminus\{u\})) \le |S\setminus\{u\}| = |S| -1.$$
Conversely, suppose that the property $q(G-S) \le |S|-1$ holds for every nonempty $S$. Fix any node $u \in G,$ and let $T$ be any subset of $V \setminus \{u\}$. Let $G_u := G - \{u\}$. Then we know that $$q(G_u -T) = q((G - \{u\}) - T) = q(G - (\{u\} \cup T))\le |T \cup \{u\}| - 1 = |T|.$$ But since $T$ is arbitrary, we conclude by Tutte's theorem that $G_u$ has a perfect matching. Further, $u$ is arbitrary, so this property holds for every choice of $u$, which is just the definition of quasi-factorisability.