For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^\star$).


An arc $(u,v)$ in $G$ is called a *shortcut* if there exists a directed path from $u$ to $v$ in $G$ different from $(u,v)$.


In our research, we came up with the following conjecture:



> 
> **Conjecture.** Let $G$ be a DAG without shortcuts such that the indegree and outdegree of every vertex is each $\leq 2$. Then there exists a matching in $G^\star$ of size at least $\frac{1}{4}e(G)$.
> 
> 
> 


Small examples seem to support this conjecture, although a general proof appears quite elusive. The lower bound $\frac{1}{5}e(G)$ here is almost trivial (and holds even with shortcuts), and with some effort we were able to prove the bound $\frac{2}{9}e(G)$. 


Any help in proving or disproving the conjecture will be appreciated.


P.S. Apparently it is crucial that $G^\star$ results from a DAG. E.g., a similar statement for a generic undirected graph of degree at most $4$ and no cycles of length $3$ (which follows from the absence of shortcuts $G$) does not hold.



Maximum matching in a graph with no "shortcuts"
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$. By [Edmonds' matching polytope theorem](http://lemon.cs.elte.hu/egres/open/Edmonds'_matching_polytope_theorem), $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. Clearly, $x^\*$ satisfies the first type of constraints, since $G^\star$ has maximum degree $4$. 


For the second type of constraints, let $S \subseteq V(G)$ with $|S| \geq 3$ and odd. Since $G$ is acyclic, $G[S]$ contains a source and a sink vertex. Thus, $H:=G^\star[S]$ contains two distinct vertices of degree at most $2$. All other vertices of $H$ have maximum degree $4$, thus 


$$
\sum\_{e \in E(S)} x^\*\_e =|E(S)|/4 =\sum\_{v \in S} \deg\_H(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$.


