Introduction to Graph Theory · Problem 2.3

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · edge-triangle-cover

Problem

Let

G = (V, E)

be a simple graph. Set

n = |V|

. Prove that we can find some edges

e_1, e_2, \ldots, e_k

G

and some triangles

t_1, t_2, \ldots, t_\ell

G

such that

k + \ell \leq n^2/4

and such that each edge

e \in E \setminus \{e_1, e_2, \ldots, e_k\}

is a subset of (at least) one of the triangles

t_1, t_2, \ldots, t_\ell

. [Remark: In other words, this exercise is claiming that all edges of

G

can be covered by at most

n^2/4

edge-or-triangles. Here, an edge-or-triangle means either an edge or a triangle of

G

, and the word ``covers'' means that each edge of

G

is a subset of the chosen edge-or-triangles.] [Hint: Imitate the above proof of Mantel's theorem.]