关于不含3正则子图图的最大边数

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

对无自环、无重边的简单图，Ｅｒｄｏｓ和Ｓａｕｃｅｒ在１９７４年提出如下问题：设 ｆ（ｐ） 是ｐ个顶点的不含３正则子图图的最大可能边数，确定ｆ（ｐ）．本文对ｐ ≥４、４≤ｐ≤４０给出了ｆ（ｐ）的下界，对４ｐ刁≤１６给出了ｆ（ｐ）的值，并对４≤ｐ ≤１５得出了所有的极图．

The authors have considered only finite undirected graphs without loops or multiple edges. In 1974 Erdos and Saucer posed the problem :Let f (p) be the maximum possible number of edges in a simple graph with p vertices which contains no 3-regular subgraph. Determine f (p). In this paper,about p≥4,4≤p≤40,giving the lower bound of f(p);about 4≤p≤16,giving the value of f(p);and about 4≤p≤15,giving all of the extreme graph.