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?

Improve this question
$\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
    Commented 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
    Commented May 26, 2022 at 15:21
  • $\begingroup$ @LouisD Shouldn't that be an answer? $\endgroup$
    – Noah Schweber
    Commented May 26, 2022 at 17:44

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Emil Jeřábek
    Commented 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$
    – Emil Jeřábek
    Commented May 27, 2022 at 12:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .