Extremal Graph Theory: Examples and False Statements

Division gives $10=3\cdot 3+1$, so the balanced sizes are $4,3,3$. Counting cross-part edges gives $4\cdot 3+4\cdot 3+3\cdot 3=33$; equivalently $\left(\genfrac{}{}{0px}{}{10}{2}\right)-\left(\genfrac{}{}{0px}{}{4}{2}\right)-2\left(\genfrac{}{}{0px}{}{3}{2}\right)=45-6-6=33$.

Turán's theorem with $r=3$ says this is $\mathrm{ex}(10,K_4)$ and that equality occurs only for $T_{10,3}$.

Every edge of $K_{3,4}$ crosses its bipartition, so a three-vertex cycle is impossible, and there are exactly $3\cdot 4=12$ possible cross edges.

Mantel's theorem gives the matching upper bound $\lfloor 7^2\mathrm{/}4\rfloor =12$, so the graph is extremal.

Every edge of $K_{3,4}$ crosses its two parts, so it has no triangle, and its edge count is $3\cdot 4=12$. Deleting an edge cannot create a triangle and changes the edge count to $11$.

Mantel's theorem gives threshold $12$ and identifies the unique equality graph as $K_{3,4}$ up to isomorphism. The edge-deleted graph therefore lies exactly one edge below the equality case.

A red clique contains at most one vertex from each of the three pairs, so it has size at most $3$. A blue clique lies within a single pair, so it has size at most $2$.

Thus $K_6$ does not arrow $(K_4,K_3)$, and the Ramsey definition gives $R(4,3)>6$, hence $R(4,3)\ge 7$.

Label the cycle vertices modulo $5$. Two adjacent vertices have no common neighbour, and two nonadjacent vertices have exactly one common neighbour. Thus no pair has the two common neighbours required to form a $K_{2,2}$.

Therefore $C_5$ is $K_{2,2}$-free. Its odd cycle is also a reminder that the host graphs in the ordinary KST problem need not themselves be bipartite.

The only cycle in $C_5$ using three edges would require a chord, and $C_5$ has only its five consecutive edges. Hence $C_5$ is triangle-free.

The graph $C_5$ is itself an odd cycle, so the cited equivalence says it is not bipartite.

Thus $C_5$ satisfies the premise and fails the conclusion, refuting the statement.

The vertices $12,34,15,23,45$ form a $5$-cycle in that order because consecutive pairs, including $45,12$, are disjoint. Hence $P$ is not bipartite and $\chi (P)\ge 3$.

Partition the ten vertices into $\{12,13,14,15\}$, $\{23,24,34\}$, and $\{25,35,45\}$. Within each class every two subsets intersect, so the Petersen adjacency definition gives no edge within a class. This is a proper three-colouring, hence $\chi (P)\le 3$.

Steps 1.1-1.2 give $\chi (P)=3$, and the density formula gives $\pi (P)=1-1\mathrm{/}(3-1)=1\mathrm{/}2$.

In a two-colouring of a cycle, colours must alternate along consecutive vertices. After the odd number $2k+1$ of edges, the closing edge would join equal colours, so no proper two-colouring exists.

Colour vertices $0,\dots ,2k-1$ alternately with two colours and give vertex $2k$ a third colour. This is proper, so $\chi (C_{2k+1})=3$. For $k=1$ this is the triangle and the same argument applies.

The density formula gives $\pi (C_{2k+1})=1-1\mathrm{/}(3-1)=1\mathrm{/}2$.

The graph $K_{2,2}$ is bipartite, so $\chi (K_{2,2})=2$. Applied to it, Erdős–Stone–Simonovits says only $\mathrm{ex}(n,K_{2,2})=o(n^2)$.

The separate common-neighbour theorem gives the strictly sharper upper bound $O(n^{3\mathrm{/}2})$. Neither statement supplies a matching lower bound here, but the improvement already shows that the Erdős–Stone–Simonovits conclusion alone does not determine even the relevant subquadratic scale.

Therefore the claimed universal determination is false. Erdős–Stone–Simonovits determines the leading quadratic density, not every lower-order extremal problem.