SUFFICIENT CONDITION FOR THE EXISTENCE OF THREE DISJOINT THETA GRAPHS

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 ≥ 12 and size at least ⌊ 11n−18 2 ⌋ contains three disjoint theta graphs. As a corollary, every graph of order n ≥ 12 and size at least ⌊ 11n−18 2 ⌋ contains three disjoint cycles of even length. 1. Terminology and introduction In this paper, we only consider finite undirected graphs, without loops or multiple edges. We use (1) for the notation and terminology not defined here. A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. Let n be a positive integer, let Kn denote the complete graph of order n and K − be the graph obtained by removing exactly one edge from K4. For a graph G, we denote its vertex set, edge set, minimum degree by V (G), E(G) and �(G), respectively. The order and size of a graph G, are defined by |V (G)| and |E(G)|, respectively. A set of subgraphs is said to be vertex-disjoint or independent, if no two of them have any common vertex in G, and we use disjoint to stand for vertex-disjoint throughout this paper. If u is a vertex of G and H is either a subgraph of G or a subset of V (G), we define NH(u) to be the set of neighbors of u contained in H, and dH(u) = |NH(u)|. For a subset U of V (G), G(U) denotes the subgraph of G induced by U. In particular, we often use (U) to stand for G(U). If S is a set of subgraphs of G, we write G ⊇ S, it means that S is isomorphic to a subgraph of G, in particular, we use mS to represent a set of m vertex-disjoint copies of S. When S = {x1,x2,...,xt}, we may also use (x1,x2,...,xt) to denote ({x1,x2,...,xt}). Let V1,V2 be two disjoint subsets or subgraphs of G, we use E(V1,V2) to denote the set of edges in G with one end-vertex in V1, while the other in V2, for simplicity, let E(x,V2) stand for E({x},V2), E(V1,x)