Example of graph $G=(V,E)$ without a perfect matching where $|N(S)|\geq |S|$ for every $S\subset V$

98 Views Asked by At

I have been asked to find a graph $G=(V,E)$ without a perfect matching where $|N(S)|\geq |S|$ for every $S\subset V$. This to show that Halls marriage theorem does not hold for non-biparite graphs but I cannot really find one graph that fulfills this.

I guess this is quite trivial but I have a hard time to really understand how to find graphs such that $|N(S)|\geq |S|$ for every $S\subset V$ without perfect matchings, does anyone have any idea about such graph?

Later on I have seen the following link, but I wonder if there is a less complicated graph?

an example for an arbitrary graph $G$ with even vertices which $\forall S \in V(G) , |N(S)|\geq |S| $ but there is no complete matching .

1

There are 1 best solutions below

1
On BEST ANSWER

The comment by @bof beat me to it, but $K_3$ will do. In fact, $K_{2k+1}$ for any positive integer $k$ will do as well.