The Extremal Function for Three Disjoint Theta Graphs

Yunshu Gao1, Lingxiu Wu1
1School of Mathematics and Computer Science, Ningxia University Yinchuan,750021, P. R. China

Abstract

A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order \(n \geq 12\) and size at least\(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint theta graphs. As a corollary, every graph of order \(n \geq 12\) and size at least \(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil ,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint cycles of even length. The lower bound on the size is sharp in general.