what-if.xkcd.com: stabbing (simply connected) regions on the 2-sphere with few geodesics

Looking at this old question again, I'm now fairly convinced that the easiest route of solving this problem is using similar ideas to the one suggested by David E Speyer in a comment, namely basically setting up a integer program after some combinatorial information (like inclusion maximal sets of states that lie on a geodesic). For example if longest_geodesics is a such a set of maximal geodesics, then the following sage code will give the answer $5$.

p = MixedIntegerLinearProgram(maximization=False)
m = p.new_variable(binary=True)
for states in all_states:
    p.add_constraint(p.sum(m[line]*(1 if (states in line) else 0) 
                     for line in longest_geodesics)>=1)
p.set_objective(p.sum(m[line] for line in longest_geodesics))
p.solve()

If we assume that the set of longest_geodesics actually contained all geodesics and that the solver actually found a correct solution, then this should be a proof that it is impossible to do with $4$ geodesics. Obtaining a complete set of geodesics (or a superset thereof) could be done by finding a complete set of "forbidden triples", i.e. triples of states that do not lie on a geodesic and then build a lattice out of all sets that do not contain any forbidden triple. I took the map data cb_2018_us_state_20m.zip from this page https://www.census.gov/geographies/mapping-files/time-series/geo/carto-boundary-file.html and found a (hopefully) complete set of longest_geodesics. And in fact the integer program didn't find a solution with only $4$ great circles. Here's one with $5$:

This is using a gnomonic projections (suggested by Martin M. W. in a comment) to make all the great circles appear as line. A more conventional map would look like this:

However some people might prefer a more human checkable proof, so I provide an argument using techniques and ideas also mentioned in other answers/comments. Throughout the argument the only assumption that is made is that certain triples of states cannot lie on a great circle.

I want to show that it is impossible to cover all $50$ states with $4$ great circles. First consider the following set of states: {'Alaska', 'Delaware', 'Hawaii', 'Kentucky', 'Vermont', 'Washington'}. I claim that any three of them cannot lie on a great circle. Therefore if those $6$ states are covered by $4$ lines, either they are split $2, 2, 2$ or $1, 1, 2, 2$, since this are the only partitions of $6$ into at most $4$ parts with size of at most $3$.

First let's consider splitting {'Alaska', 'Delaware', 'Hawaii', 'Kentucky', 'Vermont', 'Washington'} into $3$ pairs, i.e. the split $2, 2, 2$. Hence we assume that $3$ great circles each cover two of those those 6 states (and potentially many more states). We proof that one more great circle is not enough to cover all states by giving a triple of states which itself cannot lie on one great circle and each state in the triple cannot lie on any of the $3$ great circles covering the pairs in the split. For each partition we first write the split and then the triple. For example

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}

means that there is no great circle through {'Florida', 'South Carolina', 'Wyoming'} and each of these three states does not lie on a great circle containing any of the three pairs. So for example {'Florida', 'Alaska', 'Delaware'} cannot lie on a great circle and the same for {'Florida', 'Hawaii', 'Kentucky'} and {'Florida', 'Vermont', 'Washington'}. Analogously for 'South Carolina' and 'Wyoming'.

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky', 'Washington'}}: {'Rhode Island', 'Arkansas', 'Colorado'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky', 'Vermont'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Kentucky'}, {'Vermont', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Vermont'}, {'Kentucky', 'Washington'}}: {'Louisiana', 'Rhode Island', 'New Mexico'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Washington'}, {'Kentucky', 'Vermont'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Hawaii'}, {'Vermont', 'Washington'}}: {'Connecticut', 'New Mexico', 'Louisiana'}
{{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Washington'}}: {'Louisiana', 'Michigan', 'New Mexico'}
{{'Alaska', 'Washington'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Vermont'}}: {'Connecticut', 'South Carolina', 'Minnesota'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Washington'}}: {'Rhode Island', 'Arkansas', 'Colorado'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Washington'}, {'Hawaii', 'Vermont'}}: {'Rhode Island', 'Arkansas', 'Colorado'}
{{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Washington'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}}: see argument below
{{'Alaska', 'Vermont'}, {'Delaware', 'Washington'}, {'Hawaii', 'Kentucky'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Washington'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Kentucky'}}: {'Rhode Island', 'Iowa', 'North Dakota'}

For the split {{'Alaska', 'Washington'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}}, we first notice that 'Connecticut' and 'South Carolina' can't lie on any of the three great circles going through the three pairs in the split, therefore the $4$th great circle has to contain both of those. Then we look at 'Indiana' and 'Tennessee': the following triples cannot lie on a great circle:

{'Indiana', 'Washington', 'Alaska'}
{'Indiana', 'Hawaii', 'Vermont'}
{'Indiana', 'Connecticut', 'South Carolina'}
{'Tennessee', 'Washington', 'Alaska'}
{'Tennessee', 'Hawaii', 'Vermont'}
{'Tennessee', 'Connecticut', 'South Carolina'}

Therefore both 'Indiana' and 'Tennessee' must lie on the great circle containing 'Delaware' and 'Kentucky', and a contradiction is reached because the triple {'Tennessee', 'Indiana', 'Delaware'} does not lie on a great circle.

Second let's consider splitting {'Alaska', 'Delaware', 'Hawaii', 'Kentucky', 'Vermont', 'Washington'} into $4$ non-empty parts, i.e. splits of the type $1, 1, 2, 2$. Here we assume that $4$ great circles cover those $6$ states (and potentially many more states). We now consider all possible such partition (there are 45). For some of these partitions we prove that they are impossible to complete by giving a triple of states that have the following properties:

1. Each of the three states in the triple does not lie on a great circle going through any of the two parts with two elements.
2. The three states in the triple cannot lie on one great circle.
3. Each combination of two states from the triple cannot lie on the great circle through each of the two parts with one element.

From (1) it follows that the three states have to be assigned to the two parts with one element. Not all them can go to only one of them because of (2). But splitting "$3$" into two nonempty parts leaves one part with $2$ elements and this lead to a contradiction by (3). Take for example

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont'}, {'Washington'}}: {'Rhode Island', 'South Carolina', 'Arkansas'}

We have (1) because 'Rhode Island' cannot lie on the great circle through {'Alaska', 'Delaware'} nor {'Hawaii', 'Kentucky'} and analogously for 'South Carolina' and 'Arkansas'. We have (2) because {'Rhode Island', 'South Carolina', 'Arkansas'} cannot lie on a great circle. We have (3) because now matter what combination of two states you take from {'Rhode Island', 'South Carolina', 'Arkansas'}, this pair cannot lie on a great circle with 'Vermont' nor 'Washington'. Here's the list of all the partitions we can exlcude with that argument:

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont'}, {'Washington'}}: {'Rhode Island', 'South Carolina', 'Arkansas'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky'}, {'Washington'}}: {'Rhode Island', 'Arizona', 'Florida'}
{{'Alaska', 'Delaware'}, {'Hawaii'}, {'Kentucky', 'Vermont'}, {'Washington'}}: {'Utah', 'South Carolina', 'Florida'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky'}, {'Vermont'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Delaware'}, {'Hawaii'}, {'Kentucky', 'Washington'}, {'Vermont'}}: {'Louisiana', 'Oklahoma', 'Connecticut'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Vermont'}, {'Kentucky'}, {'Washington'}}: {'Arizona', 'Rhode Island', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware'}, {'Kentucky', 'Vermont'}, {'Washington'}}: {'Arizona', 'Rhode Island', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Washington'}, {'Kentucky'}, {'Vermont'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware'}, {'Kentucky', 'Washington'}, {'Vermont'}}: {'Arkansas', 'Michigan', 'Connecticut'}
{{'Alaska', 'Hawaii'}, {'Delaware'}, {'Kentucky'}, {'Vermont', 'Washington'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Vermont'}, {'Washington'}}: {'New Mexico', 'Michigan', 'Florida'}
{{'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Washington'}, {'Vermont'}}: {'Oklahoma', 'Wisconsin', 'Connecticut'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Washington'}, {'Hawaii'}, {'Vermont'}}: {'Louisiana', 'Oklahoma', 'Rhode Island'}
{{'Alaska', 'Kentucky'}, {'Delaware'}, {'Hawaii', 'Washington'}, {'Vermont'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Vermont'}, {'Delaware'}, {'Hawaii', 'Kentucky'}, {'Washington'}}: {'South Carolina', 'Michigan', 'Arkansas'}
{{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont'}}: {'Iowa', 'Connecticut', 'North Dakota'}
{{'Alaska'}, {'Delaware', 'Washington'}, {'Hawaii', 'Kentucky'}, {'Vermont'}}: {'Rhode Island', 'South Carolina', 'Arkansas'}
{{'Alaska', 'Vermont'}, {'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Vermont'}, {'Delaware'}, {'Hawaii'}, {'Kentucky', 'Washington'}}: {'Louisiana', 'Oklahoma', 'Wisconsin'}
{{'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Washington'}, {'Kentucky'}}: {'Rhode Island', 'Arizona', 'South Dakota'}
{{'Alaska'}, {'Delaware', 'Washington'}, {'Hawaii', 'Vermont'}, {'Kentucky'}}: {'Rhode Island', 'Arizona', 'Florida'}
{{'Alaska'}, {'Delaware', 'Washington'}, {'Hawaii'}, {'Kentucky', 'Vermont'}}: {'Utah', 'South Carolina', 'Florida'}
{{'Alaska'}, {'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky', 'Vermont'}}: {'Rhode Island', 'Arizona', 'South Dakota'}

For the rest of these partitions, we consider a pair such that

1. Each state the pair does not lie on a great circle going through any of the two parts with two elements.
2. The two states in the pair cannot lie on a great circle together with any of the two part with one element.

Therefore the two states in the pair have to be distributed on the two parts with one element one way or the other. We list both possible ways and the resulting partitions of the $8$ states into $4$ great circles with at least $2$ elements. Then we proof that this partition cannot be completed in either of the following two ways:

• (a) Giving a single state which cannot lie in a great circle with any of its parts
• (b) Giving three states which cannot lie in a great circle, but have to lie in one of the parts. (Which part can be seen because one of the three states will already be a state in the corresponding part).

Let's take as an example {{'Alaska', 'Kentucky'}, {'Delaware', 'Hawaii'}, {'Vermont'}, {'Washington'}}. Here a pair would be ('Arkansas', 'Rhode Island'). We have (1) because each triple {'Arkansas', 'Alaska', 'Kentucky'}, {'Arkansas', 'Delaware', 'Hawaii'}, {'Rhode Island', 'Alaska', 'Kentucky'} and {'Rhode Island', 'Delaware', 'Hawaii'} cannot lie on a great circle and we have (2) because {'Arkansas', 'Rhode Island', 'Vermont'} and {'Arkansas', 'Rhode Island', 'Washington'} cannot lie on a great circle. Hence we consider the two partitions where 'Arkansas' and 'Rhode Island' are paired with 'Vermont' and 'Washington'. For the candidate

[{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Arkansas', 'Vermont'}, {'Washington', 'Rhode Island'}]

we are in case (b). Each of 'Florida' and 'South Carolina' cannot lie in any of the great circles given by {'Delaware', 'Hawaii'}, {'Arkansas', 'Vermont'} or {'Washington', 'Rhode Island'} Therefore they must both lie on the great circle going through {'Kentucky', 'Alaska'}, but this is a contradiction since {'Florida', 'South Carolina', 'Alaska'} cannot lie on a common great circle. For the candidate

[{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Rhode Island', 'Vermont'}, {'Washington', 'Arkansas'}]

we are in case (a): the state 'New Mexico' cannot lie in a great circles going any of the pairs in the candidate. Here's list of all but one of the remaining partitions of the $6$ states into $4$ with proofs as described above:

{{'Alaska', 'Delaware'}, {'Hawaii'}, {'Kentucky'}, {'Vermont', 'Washington'}}: ('Wyoming', 'Arizona')
 [{'Delaware', 'Alaska'}, {'Hawaii', 'Wyoming'}, {'Kentucky', 'Arizona'}, {'Washington', 'Vermont'}]: Mississippi
 [{'Delaware', 'Alaska'}, {'Hawaii', 'Arizona'}, {'Kentucky', 'Wyoming'}, {'Washington', 'Vermont'}]: Connecticut


{{'Alaska', 'Hawaii'}, {'Delaware', 'Kentucky'}, {'Vermont'}, {'Washington'}}: ('Michigan', 'South Carolina')
 [{'Hawaii', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Michigan', 'Vermont'}, {'Washington', 'South Carolina'}]: Florida
 [{'Hawaii', 'Alaska'}, {'Delaware', 'Kentucky'}, {'South Carolina', 'Vermont'}, {'Washington', 'Michigan'}]: Wyoming


{{'Alaska', 'Kentucky'}, {'Delaware', 'Hawaii'}, {'Vermont'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Arkansas', 'Vermont'}, {'Washington', 'Rhode Island'}]: ['Florida', 'South Carolina', 'Alaska']
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Rhode Island', 'Vermont'}, {'Washington', 'Arkansas'}]: New Mexico


{{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky'}, {'Washington'}}: ('New Mexico', 'South Dakota')
 [{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'New Mexico'}, {'Washington', 'South Dakota'}]: Louisiana
 [{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'South Dakota'}, {'Washington', 'New Mexico'}]: Michigan


{{'Alaska', 'Washington'}, {'Delaware', 'Hawaii'}, {'Kentucky'}, {'Vermont'}}: ('North Dakota', 'Connecticut')
 [{'Washington', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'North Dakota'}, {'Connecticut', 'Vermont'}]: ['Louisiana', 'New Mexico', 'Alaska']
 [{'Washington', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Connecticut'}, {'Vermont', 'North Dakota'}]: South Carolina


{{'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky'}, {'Vermont', 'Washington'}}: ('North Carolina', 'Connecticut')
 [{'North Carolina', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Connecticut'}, {'Washington', 'Vermont'}]: ['Delaware', 'Kansas', 'Wyoming']
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'North Carolina'}, {'Washington', 'Vermont'}]: ['Oklahoma', 'North Carolina', 'South Dakota']


{{'Alaska', 'Kentucky'}, {'Delaware', 'Vermont'}, {'Hawaii'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Arkansas'}, {'Washington', 'Rhode Island'}]: Wyoming
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Rhode Island'}, {'Washington', 'Arkansas'}]: New Mexico


{{'Alaska', 'Kentucky'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Arkansas'}, {'Hawaii', 'Vermont'}, {'Washington', 'Rhode Island'}]: Kansas
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Rhode Island'}, {'Hawaii', 'Vermont'}, {'Washington', 'Arkansas'}]: New Mexico


{{'Alaska', 'Kentucky'}, {'Delaware'}, {'Hawaii'}, {'Vermont', 'Washington'}}: ('Oklahoma', 'Connecticut')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Oklahoma'}, {'Hawaii', 'Connecticut'}, {'Washington', 'Vermont'}]: Louisiana
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Connecticut'}, {'Oklahoma', 'Hawaii'}, {'Washington', 'Vermont'}]: Wyoming


{{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii'}, {'Washington'}}: ('Michigan', 'South Carolina')
 [{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Michigan'}, {'Washington', 'South Carolina'}]: Florida
 [{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'South Carolina'}, {'Washington', 'Michigan'}]: Wyoming


{{'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}, {'Washington'}}: ('North Carolina', 'Connecticut')
 [{'North Carolina', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}, {'Washington', 'Connecticut'}]: ['Delaware', 'Oklahoma', 'Louisiana']
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}, {'Washington', 'North Carolina'}]: Florida


{{'Alaska', 'Washington'}, {'Delaware', 'Kentucky'}, {'Hawaii'}, {'Vermont'}}: ('Michigan', 'South Carolina')
 [{'Washington', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Michigan'}, {'South Carolina', 'Vermont'}]: ['Iowa', 'North Dakota', 'Hawaii']
 [{'Washington', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'South Carolina'}, {'Michigan', 'Vermont'}]: Connecticut


{{'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Washington'}, {'Vermont'}}: ('Iowa', 'Connecticut')
 [{'Iowa', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Washington', 'Hawaii'}, {'Connecticut', 'Vermont'}]: Michigan
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Kentucky'}, {'Washington', 'Hawaii'}, {'Iowa', 'Vermont'}]: South Carolina


{{'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii'}, {'Vermont', 'Washington'}}: ('North Carolina', 'Connecticut')
 [{'North Carolina', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Connecticut'}, {'Washington', 'Vermont'}]: ['Delaware', 'Oklahoma', 'Louisiana']
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'North Carolina'}, {'Washington', 'Vermont'}]: Wyoming


{{'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Kentucky'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Vermont'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Rhode Island'}]: ['Hawaii', 'New Mexico', 'Ohio']
 [{'Rhode Island', 'Alaska'}, {'Delaware', 'Vermont'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Arkansas'}]: Michigan


{{'Alaska'}, {'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont', 'Washington'}}: ('Connecticut', 'Arkansas')
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Arkansas'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Vermont'}]: South Carolina
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Connecticut'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Vermont'}]: ['Hawaii', 'New Mexico', 'Ohio']


{{'Alaska', 'Vermont'}, {'Delaware', 'Washington'}, {'Hawaii'}, {'Kentucky'}}: ('Wyoming', 'Arizona')
 [{'Alaska', 'Vermont'}, {'Washington', 'Delaware'}, {'Hawaii', 'Wyoming'}, {'Kentucky', 'Arizona'}]: Mississippi
 [{'Alaska', 'Vermont'}, {'Washington', 'Delaware'}, {'Hawaii', 'Arizona'}, {'Kentucky', 'Wyoming'}]: ['Maine', 'Connecticut', 'Alaska']


{{'Alaska', 'Washington'}, {'Delaware', 'Vermont'}, {'Hawaii'}, {'Kentucky'}}: ('North Dakota', 'Rhode Island')
 [{'Washington', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'North Dakota'}, {'Kentucky', 'Rhode Island'}]: Iowa
 [{'Washington', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Rhode Island'}, {'Kentucky', 'North Dakota'}]: ['Oklahoma', 'Washington', 'Arizona']


{{'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii'}, {'Kentucky', 'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Rhode Island'}, {'Washington', 'Kentucky'}]: New Mexico
 [{'Rhode Island', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Arkansas'}, {'Washington', 'Kentucky'}]: Michigan


{{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky'}}: see argument below

{{'Alaska'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky', 'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Rhode Island'}, {'Hawaii', 'Vermont'}, {'Washington', 'Kentucky'}]: New Mexico
 [{'Rhode Island', 'Alaska'}, {'Delaware', 'Arkansas'}, {'Hawaii', 'Vermont'}, {'Washington', 'Kentucky'}]: Colorado


{{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii'}, {'Kentucky', 'Vermont'}}: ('Michigan', 'South Carolina')
 [{'Washington', 'Alaska'}, {'Delaware', 'Michigan'}, {'Hawaii', 'South Carolina'}, {'Kentucky', 'Vermont'}]: Rhode Island
 [{'Washington', 'Alaska'}, {'Delaware', 'South Carolina'}, {'Hawaii', 'Michigan'}, {'Kentucky', 'Vermont'}]: ['Washington', 'New Mexico', 'Kansas']

For the only remaining partition, namely {{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky'}} we provide the following ad-hoc argument: We use the fact that following states cannot lie on the great circles through any of the the part {'Alaska', 'Washington'} nor {'Hawaii', 'Vermont'}:

['South Carolina', 'West Virginia', 'Tennessee', 'Illinois', 'Rhode Island']. 

Therefore 'South Carolina' must either lie on a great circle with 'Delaware' or 'Kentucky'. Assume 'South Carolina' and 'Delaware' lie on a great circle with 'Delaware'. On this great circle we cannot also have any of 'West Virginia', 'Tennessee' and 'Illinois', which therefore must lie on the great circle through 'Kentucky', but this is a contradiction, since 'West Virginia', 'Tennessee' and 'Illinois' cannot lie on a great circle. Therefore 'South Carolina' has to lie on the same great circle as Kentucky. Since 'Rhode Island' does not lie on a great circle with 'Kentucky' and 'South Carolina', we have to assume that it lies on the same great circle as 'Delaware', which leaves us with the following partition:

[{'Alaska', 'Washington'}, {'Delaware', 'Rhode Island'}, {'Hawaii', 'Vermont'}, {'Kentucky', 'South Carolina'}],

which can be seen to be absurd with the method described above by considering ['Arkansas', 'New Mexico', 'Washington'], i.e. both 'Arkansas' and 'New Mexico' can only lie on the part with 'Alaska', but at the same time cannot lie on a great circle with it.

This now got a little longer that I expected; I do like the proof using integer programming better.

It is known to be NP-hard to cover regions (or even just points) with a minimum number of lines. For the Euclidean plane, see Megiddo, Nimrod and Tamir, Arie (1982), "On the complexity of locating linear facilities in the plane", Oper. Res. Lett. 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6. Their construction is flexible enough that, at least for the region version, it should extend to the approximations to Euclidean geometry that one gets in small patches of spherical geometry.

I think the easiest route to a lower bound is to pick four states such as Hawaii, Alaska, Rhode Island, and Florida, and show that any geodesics cutting them leave too many states uncovered, or are five or more in number. It should be possible to enumerate the maximal cutting geodesics for each pair of states, and then argue using such numbers. Even trying all combinations of four cutting geodesics involving more than six states should be tractable, say on order of 10^15 combinations or so.