不含3正则子图的图的最大可能边数的下界

Lower-bound of maximum possible number of edges in simple graph containing no 3-regular subgraph

１９７４年，Ｅｒｄｓ和Ｓａｕｃｅｒ提出如下问题：设ｆ（ｐ）是ｐ个顶点的不含３正则子图的图的最大可能边数，确定ｆ（ｐ）．本文给出：（１）ｆ（ｐ）≥３ｐ－９，ｐ≥４；（２）ｆ（ｐ）≥３ｐ－５，ｐ≥３４．

The authors have considered only finite undirected graphs without loops or multipleedges. In 1974 Erdos and Saucer possed the problem:Let f(p)be the maximum possiblenumber of edges in a simple graph with p vertices which contains no 3-regular subgraph fordetermining f(p).The following bounds are given,(1)f(p)≥3p-9, for p≥4;(2)f(p)≥3p-5,for p≥34.