We will use the method of alteration. The first step is to randomly color the lines blue, i.e. color a line blue with probability ( will depend on ). Note that the expected number of blue lines is . Now, we will remove blue lines in a deterministic way such that there are no more blue regions (this is the alteration part).

We will now find the expected number of blue regions. The first step is to count the number of total regions. The way we do this is consider a graph whose vertices are the intersection points. Note that we then have vertices. The edges will be the finite line segments between adjacent vertices on a line. Then, there are edges (since each line has edges). Therefore, by Euler's formula we have that , so . Now, any region is picked with probability at most since there are at least lines bounding it, and , so by linearity of expectation, the expected number of blue regions is at most .

Now, the idea is to pick . Now, for each blue region, we remove one line, so we remove at most . Therefore, the expected number of blue lines left is at least . This means that there is some coloring with at least blue lines that has no blue regions since the expected number of blue lines in a properly chosen such coloring is .