# Is König's Property for graphs inheritable from finite subgraphs?

Let $$G = (V,E)$$ be a simple, undirected graph. A set $$C \subseteq V$$ is said to be a (vertex) cover if $$C \cap e \neq \emptyset$$ for all $$e\in E$$. A matching is a set $$M\subseteq E$$ of pairwise disjoint edges (elements of $$E$$).

We say that $$G$$ has König's Property if there is a matching $$M\subseteq E$$ and a cover $$C\subseteq V$$ satisfying

1. $$|C \cap e| = 1$$ for all $$e\in M$$, and
2. $$C \subseteq \bigcup M$$.

Question. Suppose $$G = (V,E)$$ is a graph such that for all finite subsets $$E_0\subseteq E$$ the graph $$(V, E_0)$$ has König's Property. Does this imply that $$G$$ has König's Property?

• If this is named after the eponym of Kőnig's theorem, then note that that name is spelt with ‘ő’, not ‘ö’. May 26, 2022 at 14:14
• If every finite subgraph of $G$ satisfies K\"onig's Property, then $G$ has no odd cycles and is thus bipartite. Aharoni (K\"onig's Duality Theorem For Infinite Bipartite Graphs) proved that if $G$ is bipartite, then $G$ satisfies K\"onig's property. May 26, 2022 at 15:21
• @LouisD Shouldn't that be an answer? May 26, 2022 at 17:44

If every finite subgraph of $$G$$ satisfies Kőnig's Property, then $$G$$ has no odd cycles and is thus bipartite. Aharoni (König's Duality Theorem For Infinite Bipartite Graphs) proved that if $$G$$ is bipartite, then $$G$$ satisfies Kőnig's property.
• Markdown note: K\"onig doesn't work (it renders as K"onig). Actually, Dénes Kőnig is spelt like so, not König as would be produced by TeX from K\"onig—although apparently his father published as Julius König. I have edited accordingly. May 27, 2022 at 1:30
• Why does $G$ have no odd cycles? For example, let $G$ consist of a triangle $\{x,y,z\}$ with two extra leaves $u,v$ attached to $x$ and $y$, respectively. Then $G$ has the Kőnig property, taking $C=\{x,y\}$ and $M=\{\{x,u\},\{y,v\}\}$. Or am I missing something? May 27, 2022 at 12:36
• Oh, I see: $G$ itself has the Kőnig property, but not all its subgraphs. Never mind. May 27, 2022 at 12:52