# Reference Request - Tutte-matching-theorem type conditions for ${P_3}$-packings of graphs

A well-known Theorem of Tutte gives a sufficient and necessary condition for a graph to have a perfect matching (i.e., perfect $$P_2$$-packing):

A graph $$G$$ has a perfect matching if and only if, for every subset $$S$$ of $$V(G)$$, the number of odd components of $$G-S$$ is at most $$|S|$$. Symbolically, $$\forall S\subseteq V(G), |S| \geq \text{odd}(G-S)$$

My question is this: What analogues of this result are known for perfect $$P_3$$-packings? I know that the problem of determining whether partitioning the vertices of a graph into copies of $$P_3$$ is in general NP hard, so maybe a necessary and sufficient condition is a bit of a stretch. But I am interested in any result of this kind, sufficient and / or necessary, possibly for limited classes of graphs.

To be specific, I am looking for conditions of the following form:

The graph $$G$$ has a perfect $$P_3$$-packing if / only if, for every subset $$S$$ of $$V(G)$$, we have $$|S|\geq f(G-S)$$ where $$f: \mathcal{G}\to \mathbb{R}$$ is some function that takes a graph $$H$$ and returns a number that depends on the size and number of the components of $$H$$.

Terminology: A perfect $$P_n$$-packing of a graph is a partition of the vertex set of the graph so that each part of the partition induces a subgraph with a spanning path $$P_n$$.

A perfect matching of a graph is a set of edges that partition the vertex-set of the graph (i.e., a perfect $$P_2$$-packing).

$$\text{odd}(H)$$ is the number of components of the graph $$H$$ that have an odd number of vertices.

$$P_3$$-packings are also sometimes known as $$\Lambda$$-packings, and perfect $$P_3$$-packings are sometimes called $$P_3$$-factors or $$\Lambda$$-factors.

Here's one possible condition of this form; it is necessary, but not sufficient.

For a graph $$G$$ with connected components $$G_1, G_2, \dots, G_k$$, let $$o_{m}(G) = \sum_{i=1}^k (|V(G_i)| \bmod m)$$. This generalizes the function in Tutte's theorem: $$o_2(G)$$ just counts the number of odd components in $$G$$.

If $$G$$ has a perfect $$P_3$$-packing, then we must have $$|S| \ge \frac12 o_3(G-S)$$ for all $$S \subseteq V(G)$$. The reasoning is: the best $$P_3$$-packing in $$G-S$$ must leave at least $$o_3(G-S)$$ vertices uncovered, because it leaves at least $$|V(G_i)| \bmod 3$$ vertices of $$G_i$$ uncovered for each $$i$$. Therefore in a perfect $$P_3$$-packing of $$G$$, the uncovered vertices must be covered by copies of $$P_3$$ that overlap $$S$$. We need a vertex of $$S$$ for every two uncovered vertices of $$G-S$$: a copy of $$P_3$$ split between $$S$$ and $$G-S$$ can, at best, have one vertex from $$S$$ and two from $$G-S$$. The inequality follows.

The smallest graph for which this condition is not sufficient is the net graph:

This has no perfect $$P_3$$-packing, but satisfies the $$o_3$$ condition:

• When $$|S|=0$$, the condition is satisfied because the number of vertices is divisible by $$3$$.
• When $$|S|=1$$, $$G-S$$ can either have one component of size $$5$$ or two of size $$1$$ and $$4$$. Both give $$o_3(G-S)=2$$, which is fine.
• When $$|S| \ge 2$$, then $$|V(G-S)| \le 4$$, so $$o_3(G-S) \le 4$$ and the condition can't fail.

Experimentally, though, the condition is not too weak. Mathematica's GraphData database knows $$7$$ connected $$6$$-vertex graphs with no perfect $$P_3$$-packing, $$44$$ connected $$9$$-vertex graphs with no perfect $$P_3$$-packing, and $$11$$ connected $$12$$-vertex graphs with no perfect $$P_3$$-packing. Of these, only two satisfy the $$o_3$$ condition for all sets $$S$$: the net graph, and a graph obtained from this one by adding leaves to the four degree-$$3$$ vertices. (I should point out that for large numbers of vertices, Mathematica's graph database is not necessarily representative, but it's what I had lying around.)

As a matter of complexity theory, we shouldn't hope very hard for a necessary and sufficient condition like this; let me summarize why. If we had one, and if the function $$f(G-S)$$ were efficiently computable, it would put the $$P_3$$-packing problem in co-NP: it would give a short, efficiently checkable proof that a graph has no $$P_3$$-packing. We do not expect NP-complete problems to be in co-NP: though this does not imply P=NP, it still makes the polynomial hierarchy sad.

• Thanks for the detailed answer! The function you found is what I had in mind so far, and was rather hopeful that there was some refinement of it known / some good class of graphs for which it was sufficient, but alas. (It is sufficient for graphs that are both claw and net-free, but for silly reasons). Commented May 24, 2022 at 17:32