Skip to main content
1 of 4
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, your conjecture is true, even without the assumption that $G$ does not contain shortcuts. The following proof is due to Sam Fiorini.

Proof. Let $P \subseteq \mathbb{R}^{E(G^\star)}$ be the matching polytope of $G^\star$. That is, $P$ is the convex hull of the set of characteristic vectors of matchings of $G^\star$. Edmond's proved that $P$ consists of all $x \in \mathbb{R}_{\geq 0}^{E(G^\star)}$ such that

$\sum_{e \in \delta(v)} x_e \leq 1$, for all $v \in V(G^\star)$

and

$\sum_{e \in E(S)} x_e \leq \frac{|S|-1}{2}$, for all odd $S \subseteq V(G^\star)$.

Here $\delta(v)$ is the set of all edges incident to $v$, and $E(S)$ is the set of edges with both endpoints in $S$.

Now, let $x^*$ be the vector such that $x_e^*=\frac{1}{4}$, for all $e\in E(G^\star)$. We show that $x^*$ is in the matching polytope of $P$. Clearly, $x^*$ satisfies the first type of constraints, since $G^\star$ has maximum degree $4$.

For the second type of constraints, let $S$ be an odd-size subset of vertices. Since $G$ is acyclic, $G[S]$ contains a source and a sink vertex. Thus, $G^\star[S]$ contains two distinct vertices $a$ and $b$ of degree at most $2$. All other vertices of $G^\star[S]$ have maximum degree $4$, thus

$$ \sum_{e \in E(S)} x_e =|E(S)|/4 =\sum_{v \in S} \deg(v)/8 \leq (|S|-1)/2. $$

Thus, the vector $x^*$ can be written as a convex combination of matchings, which in particular implies that there must be a matching of size at least $e(G)/4$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187