Vtyjkyuk

I have a graph $G$, and I would like to obtain a set $S$ of subgraphs of $G$ such that:

• every subgraph in $S$ is chordal;


• the subgraphs in $S$ are pairwise edge-disjoint;


• every triangle in $G$ is witnessed in some subgraph in $S$;


• the set $S$ is minimal, i.e., each subgraph in $S$ should contain as many triangles as possible.

Please note that I do not wish to compute such a set, I just want to use it in a proof and I would like to know if it is obvious that such a set exists or if I have to prove it.

My intuition says that such a set exists, but I do not know how to phrase it in a formal manner.

Such a set does not always exist. For example, take the $6$-vertex wheel graph:

Take a subgraph from $S$ containing one of the triangles. Then it must also contain the next adjacent triangle: it already includes one of its edges, so no other element of $S$ can contain that triangle, but some element of $S$ must. By repeating this argument, the subgraph we start with must contain all five triangles, so it must be the entire graph $G$. But $G$ is not chordal, so this violates the first condition.

The answer to the question in your title, though, is yes: if we drop the condition that every triangle is present in one of the subgraphs, then such a set $S$ does exist. One such set is the set of all $1$-edge subgraphs; this is probably not minimal, but now that we know that the collection of such partitions is nonempty, we can take one with as few parts as possible. (There may be multiple ways to achieve that minimum.)