Can any data be learned using polynomial logistic regression We know that a Taylor polynomial can approximate any continuous function. As @DemetriPananos noticed, Logistic regression seeks to estimate the coefficients for a model and any cut off is imposed post facto. But suppose there's a best possible decision boundary for our data. By "best possible" I mean a decision boundary that perfectly separates two classes.
Assume, for the sake of simplicity, that there is no data points from positive class that overlay data points from negative class (as @Sycorax suggested). For example consider this plot:

The blue line perfectly separates two classes. But the blue line itself doesn't represent a function.

*

*If we were to increase a degree of polynomial in our logistic regression, can we be sure that such a perfect decision boundary would be found for any data that can be perfectly separated?


*If the answer to my first question is "yes", then how to prove (or show) it?

There are a few problems with your first paragraph which may make your question difficult to answer.

We know that a polynomial can approximate any function.

Can it?  If you're referring to a Taylor polynomial, then the function must be smooth.  Not every function is a smooth function.

In binary logistic regression we're trying to fit a decision boundary to our data.

This isn't true.  Logistic regression seeks to estimate the coefficients for a model
$$ p(x) = \dfrac{1}{1 + \exp(-x^T\beta)} $$
There is no decision boundary here, and any cut off is imposed post facto.
