On subgraphs of tripartite graphs

A central problem in graph theory is studying under which conditions a graph contains another graph as a subgraph. A well known theorem of Turan determined the minimum number of edges that forces a graph to contain a complete subgraph on t vertices for arbitrary t.

In 1975, Bollobas, Erdos, and Szemeredi investigated the minimal degree condition that forces a tripartite graph with n vertices in each part to contain an octahedral graph. They provided a lower bound without a proof and an upper bound with a proof.

We verify their lower bound and correct a mistake in their proof, thus providing a new upper bound.