4 votes

Minimum number of triangles required to cover a complete graph?

This problem is the subject of (and was completely solved in) the paper "M. K. Fort Jr. and G. A. Hedlund. Minimal coverings of pairs by triples. Pacific Journal of Mathematics, 8(4):709–719, ...
Nathaniel Johnston's user avatar
3 votes

property of minimal triangulations

As @Laakeri commented, the connection between triangulations and minimal separators can be used to show this property. Based on the definitions: A subset $S \subseteq V$ is an $a, b$-separator of $G$ ...
Marko Lalovic's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible