Question 157
Find the smallest positive number $0 \lt c \lt 1$ satisfying the following property:
Any simple, triangle-free graph with $n \ge 3$ vertices, where the degree of any vertex is strictly bigger than $cn$, is bipartite.
**Explanation:** A simple graph is an undirected graph with no loops and no multiple edges. The degree of a vertex is the number of edges connected to that vertex. A triangle is a cycle of length three. A graph is bipartite if it can be colored in two colors in such a way that no edge connects vertices of the same color.
Any simple, triangle-free graph with $n \ge 3$ vertices, where the degree of any vertex is strictly bigger than $cn$, is bipartite.
**Explanation:** A simple graph is an undirected graph with no loops and no multiple edges. The degree of a vertex is the number of edges connected to that vertex. A triangle is a cycle of length three. A graph is bipartite if it can be colored in two colors in such a way that no edge connects vertices of the same color.