What’s the Chance a Random Problem Has a Solution?
Consider a graph, which is a set of vertices connected with edges. Your task is to assign two colors to the vertices of the graph, but under the constraint that if vertices share an edge, then they must be different colors. Can you solve this problem and satisfy the constraint? Now suppose that the edges of the graph are chosen randomly; for example, by flipping a coin for every two vertices to determine if there is an edge connecting them. What’s the chance that you can still find a coloring which satisfies the constraint?