Brain teaser solution in Graph Theory / Ramsey Theory I have a solution to the following brainteaser, which I think is the correct answer, but I haven't been able to come up with a way to prove that it's the right answer. I know very little about graph theory, and even less about Ramsey theory, but this feels applicable.

You are camping with your friends. You have a flashlight for any emergency and have brought 8 batteries along with you. Your brother calls to tell you that four of those batteries are already dead.
  Your flashlight requires two working batteries to run. What is the least number of pairs you will need to test to guarantee that you can get the flashlight on?
Note that the final time you load the working batteries into flashlight counts as a test, even if you already know that the pair works.

My solution is as follows (spoiler):

 Partition the batteries into four disjoint pairs. Test each pair. If any of them work, great, you're done. If none of them work, you know that each pair has exactly one good battery, and one bad battery.
 

 Now take two of the four pairs. Test each battery from one pair with each battery of the other pair. I.e., if the pairs are $(A,B)$ and $(C,D)$, then test $(A,C)$, $(A,D)$, $(B,C)$, and $(B,D)$. Since one of $A$ and $B$ works, and one of $C$ and $D$ work, one of these four trials will work.
 

 So the total number of tests is eight, and you're guaranteed to find at least one pair of good batteries.
 

 Note: Sisi has offered a better solution in the comments which can do it in seven tests.

I know my solution works to find a working pair, but how would I prove that there isn't a way to do it in fewer tries (or, if there is a better solution, how would you prove that it is the best solution)?
 A: As @Sisi noted, you can find working pair in $7$ tests by splitting the batteries $3,3,2$. 
Now, how could we prove that no $6$ tests suffice? The tests one does can be represented as edges in a graph of $8$ vertices. We would like to prove that we can color $4$ vertices of the graph black (dead), so that no edge gets both of its vertices white (working), that is, that there always exists a (black) vertex cover of size $4$.
To do this, pick the vertex of the highest degree, color it black and remove from the graph with all its incident edges. If we have removed three or more edges, then there are at most 3 left which are easy to cover with the remaining 3 black vertices. If we have removed two edges, then the next vertex of the highest degree (in the smaller graph) also has degree at least 2 (since we have 4 edges remaining and 7 vertices). In this case, we remove two more edges and its easy to cover the rest with the remaining two black vertices. This concludes the proof.
Edit: The previous version was wrong, thanks to @Greg Martin for pointing out the flaw.
I hope this helps $\ddot\smile$
