Grinberg-Introduction-Graph-Theory · Problem 2.1

Simple graphs

Mathematics — Graph Theory · ramsey-theory-triangle-anti-triangle

Problem

Let

G

be a simple graph. A triangle-or-anti-triangle in

G

means a set that is either a triangle or an anti-triangle. (a) Assume that

|V(G)| \geq 6

. Prove that

G

has at least two triangle-or-anti-triangles. (For comparison: Proposition 2.3.1 shows that

G

has at least one triangle-or-anti-triangle.) (b) Assume that

|V(G)| = m + 6

for some

m \in \mathbb{N}

. Prove that

G

has at least

m + 1

triangle-or-anti-triangles.