Motivation: What restrictions would allow us to replace the condition in Tutte's theorem for perfect matching by just Hall's condition.
Extension of Hall's condition for general graphs: If for all independent sets $S \subseteq V$ in a graph satisfy $N(S) \geq |S|$, where $N(S)$ denotes the cardinality of the neighbor set of $S$ and $V$ is the vertex set.
Does there exist an infinite family of graphs such that:
- $|V| = n$ is even and the graph is connected.
- They satisfy the above condition.
- Tutte's theorem is violated i.e. there is no perfect matching.
- Every vertex has degree $\geq \Omega(n)$.
Note that if you relax the condition 4 to just being a dense graph you can get such graphs with joining $K_{2r}$ to any graph satisfying the first 3 conditions by an edge. Similarly, if the graph is allowed to be disconnected you can have a disjoint union of two odd cliques.
If there are such graphs what extra conditions would ensure that there are no such graphs?
Example. For each positive integer $n,$ let $G_n$ be the graph of order $6n+4$ obtained by adding a new vertex $p$ to the graph $3K_{2n+1}$ and edges joining $p$ to all the other vertices.