So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding why the proof of proposition 5 works in proving the statement.
My understanding of the proof is that we assume there's a DFA consisting of $<n$ states and we construct $n$ strings. We then use the pigeonhole principle which would mean that two of these strings would have to be in the same state meaning that if we append a new string to both of these strings that are currently in the same state, these new strings should either both be accepted or rejected. This is where we want the contradiction.
I have two questions,
1) Do we have to make strings such that each would be in its own state or can we just make a set of any $n$ strings and so long as we can append something to each pair such that one of the strings in the pair is accepted and the other, rejected (leading to a contradiction)?
2) Does the proof imply that there is a DFA of exactly six states or just that there aren't any DFAs of five, four, three, two,or one state(s)?