4
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ If this is named after the eponym of Kőnig's theorem, then note that that name is spelt with ‘ő’, not ‘ö’. $\endgroup$
    – LSpice
    May 26, 2022 at 14:14
  • 3
    $\begingroup$ 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. $\endgroup$
    – Louis D
    May 26, 2022 at 15:21
  • $\begingroup$ @LouisD Shouldn't that be an answer? $\endgroup$ May 26, 2022 at 17:44

1 Answer 1

4
$\begingroup$

(Just making my comment an answer as suggested.)

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – LSpice
    May 27, 2022 at 1:30
  • 1
    $\begingroup$ 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? $\endgroup$ May 27, 2022 at 12:36
  • 1
    $\begingroup$ Oh, I see: $G$ itself has the Kőnig property, but not all its subgraphs. Never mind. $\endgroup$ May 27, 2022 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.