Vertices in blue are elements of set S.
$|S|=14, o(G-S)=16 > |S|$.
By Tutte’s thm, there is no p.m. in this graph.
Use the same construction as in Petersen’s thm to get bigraph $D’=(X,Y)$: $\forall x,y \in V(D), ((x,y) \in E(D) \iff x' \in X, y'' \in Y, (x', y'') \in E(D'))$.
According to Hall’s thm, since $\forall S \subset X(D’), |N_{D}(S)| \ge |S|$, D’ has a matching M covering all out-vertices. Since |X| = |Y|, all vertices are covered by M.
Putting M back to D gives a 2-factor, since every vertex has exactly one in-degree and 1 out-degree. 2-factor exactly consists of some pairwise disjoint cycles in D.
The pairwise disjoint cycles in D make a 2-factor F.
$\forall S \subset V(D), |N^+(S)| = |N^+{F}(S)| + |N^+{G \setminus F}(S)| \ge |N^+_{F}(S)| = |S|$.
According to Peterson’s thm, 3-regular graph with no cut edges will have p.m. Then we’ll want to add more cut edges.
In the below construction, there’re $56+4=34$ vertices. Edges in red is in matching M with size $26+3=15$, which is no more than $n/2-2=15$. M is the maximum matching, since no M-augmenting path exist (all non-cover vertices are in blue and no any alternating path connects them).
Suppose there is a 9-regular connected graph G s.t. it remains connected after deleting any 7 edges but has no p.m.