The number of edges of the edge polytope of a finite simple graph

Takayuki Hibi, Aki Mori, Hidefumi Ohsugi, Akihiro Shikama


Let d ≥ 3 be an integer. It is known that the number of edges of the edge polytope of the complete graph with d vertices is d(d − 1)(d − 2) / 2. In this paper, we study the maximum possible number μd of edges of the edge polytope arising from finite simple graphs with d vertices. We show that μd = d(d − 1)(d − 2) / 2 if and only if 3 ≤ d ≤ 14. In addition, we study the asymptotic behavior of μd. Tran–Ziegler gave a lower bound for μd by constructing a random graph. We succeeded in improving this bound by constructing both a non-random graph and a random graph whose complement is bipartite.


Finite simple graph, edge polytope

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications