28个顶点的简单MCD图

Simple MCD-Graphs on 28 Vertices

设Ｓｎ是ｎ个顶点的没有等长圈的简单图的集合．若Ｇ∈Ｓｎ且Ｓｎ中不存在图Ｇ＇使｜Ｅ（Ｇ＇）｜＞｜Ｅ（Ｇ）｜，则称图Ｇ是简单ＭＣＤ图．若简单ＭＣＤ图Ｇ是２连通的，则称Ｇ是２连通简单ＭＣＤ图．本文证明了不存在具有２８个顶点的含有同胚于Ｋ４的子图的２连通简单ＭＣＤ图．于是结合ＤｉｓｃｒｅｔｅＭａｔｈ．１２６（１９９４），我们完全证明了下述定理：存在ｎ个顶点的含有同胚于Ｋ４的子图的２连通简单ＭＣＤ图当且仅当ｎ∈｛１０，１１，１４，１５，１６，２１，２２｝．

Let Sn be the set of simple graphs on n venices in which no two cycles have the same length. A graph G is called a simple MCD-graph if there exists no graph G' in Sn with |E (G')|>|E (G)|. A simple MCD-graph G is called a 2-connected simple MCD-graph if G is a 2-connected graph. In this paper we prove that there does not exist a 2-connected simple MCD-graph on 28 vertices containing a subgraph homeomorphic to K4. Consequently the following theorem stated in Discrete Math. 126 (1994) 325￣338 is flawless: 'There exists a 2-connected simple MCD-graph on n vertices containing a subgraph homeomorphic to K4 if and only if n∈e { 10, 11, 14, 15, 16, 21,22}.