Dense Triangle-Free Graph - Math Problems | Repovive

MATH5. Dense Triangle-Free Graph Beta

Let $G$ be a finite simple undirected graph on $n\ge1$ vertices. Suppose that $G$ contains no triangle and every vertex has degree greater than $2n/5$ .

Prove that $G$ is bipartite.

Show that the bound is optimal by constructing, for every positive integer $t$ , a triangle-free, non-bipartite graph on $5t$ vertices with minimum degree $2t$ .

Proof

You can write formulas in LaTeX or in plain text, and write your solution in any language.

Let $G$ be a finite simple undirected graph on $n\ge1$ vertices. Suppose that $G$ contains no triangle and every vertex has degree greater than $2n/5$ .

Prove that $G$ is bipartite.

Show that the bound is optimal by constructing, for every positive integer $t$ , a triangle-free, non-bipartite graph on $5t$ vertices with minimum degree $2t$ .