We claim that for some fixed . It is easy to see that this works. First, we show that for all constant polynomials . It is obvious that by induction. Note that , so if , so , so , so or . We also have , so , or , or or . Thus, , so . Let . We will now show that for all .

We see that for any integer , so . But , so we must have for all integers . Thus, we can make sufficiently large to derive a contradiction, unless , so we must have , as desired.

During the test, I basically had this solution, but I over complicated it a lot. I think I was trying to look at the explicit coefficients of . I guess the test pressure got to me

For each edge , create a variable . This variable is if the edge is present in the new graph obtained by deletion, and is otherwise. Now suppose for some vertex , are the two edges directed out, and are the two edges directed in. We want exactly one of to be present, and exactly one of to be present. You can easily check that this is equivalent to demanding that and . So finding such deletion graphs is equivalent to solving all these linear equations where all the variables are in .

Now you may be asking, "where is the mod 2 coming in"? The reason is that the solution space is for some , which is not natural to work with. However, we can replace with , or the integers mod 2, which is a field. This means that we can use Linear Algebra. Note that those equations that we wrote are equivalent to the same equations mod 2. Therefore, we have some huge system of linear equations over a field. The idea from linear algebra is that the set of solutions is a vector subspace of , so its size is , where is the dimension of that vector space.

It suffices now to show that , or that there are at least two solutions. In fact, swapping deleted with not deleted, it suffices to show the existence of just one solution. This can be done greedily, here is a sketch: the idea is to delete an edge, look at the two edges - one that shares a tail with the original edge, one that shares the tip. Then those must be not deleted, so each of those edges have another edge that must be deleted, and so on until we form a cycle. Then we delete that cycle and repeat.

The later ideas basically form a solution, but its hard to write out the details (in particular, I feel like showing this "alternating cycle decomposition" exists and unique is tricky to do formally. Of course, its really obvious, and probably twenty minutes of careful thought would do the trick.

Firstly, note that if is the midpoint of , then , so is cylic. But has diameter , so is the foot from to . Also, if is the arc midpoint of on , then has center . These two observations allow us to draw an accurate diagram, as well as get rid of .

---

How to construct diagram:
Let be any point, let be any point, and let be on the circle with center and radius . Then, let be the second intersection of (center passes through ) with . Finally, let be the intersection of the perpendicular to at with .

---

From this construction alone, we will be able to prove an important lemma.
Lemma:
Proof of Lemma: We use complex numbers with , , and . Note then that . We see that is real and satisfies , so we have
We have that , so is pure imaginary. Thus, , or . Therefore,
as desired.

---

We now proceed with the rest of the solution. Let be on such that (this is motivated by the fact that we want the pole of wrt to lie on , and the fact that ). We claim that is the desired concurrence.

Let be the midpoint of . By the above mentioned motivation, we have that collinear. Note that is the angle between (the perpendicular bisector of ) and (since ). This is simply , so since , we have that . Thus, , so by the lemma, we have that . Thus, the inverse of about is , and since the inverse of is , we then have that .

We want to show that the tangents at to concur at , or that the polar of wrt is . But the inverse of is in , so the polar passes through . By the motivation of the definition of , we have that the polar is parallel to . Therefore, since collinear, the polar of wrt is , as desired.

We now want to show that the polar of with respect to is , or (now we basically got rid of , we'll still use it to make the angle chases cleaner). We see that
so is tangent to . Therefore, it suffices to show that the polar of wrt passes through . By Lahire, it suffices to show that is on the polar of . We see that
so is tangent to . Let . Since , we must have that is the other tangent, so the polar of is , or the radical axis of and .

However, we have that the power of with respect to is , and the power of with respect to is . Since , there is a rotation at that sends and , so , so has equal power with respect to and , so is on the radical axis of and , which is the polar of . Therefore, as we noted before, by Lahire, the polar of wrt is . This completes the proof.

This one took me a while. I had basically figured out the whole solution modulo the lemma in about 1-2 hours, but the lemma stumped me for way too long than it should have. Only after an hour banging my head with inversion and trying to do clever power of point stuff did I realize the complex bash was immediate. I wonder if there is a nice synthetic solution to it (that only uses the basic setup, basically only).