Referee says the proof is wrong, but it is not, what to do?

While you might be able to appeal to the editor, once you've been rejected, you're probably not going to get a change in decision. I would instead recommend focusing on a new submission to another journal.

Before you do so, however, I would strongly advise performing a major revision on your presentation of the proofs. Assuming that your proofs are in fact correct, you clearly did not convey them in such a way that their correctness and significance were obvious to the reviewer. The reviewer may have been a sloppy or shallow reader, but so in fact will be many of your other readers after publication.

In short, take the feedback as an indicator of how your paper needs to be improved before you submit it to another journal.

I must disagree with some of the answers.

Some assume that it is a problem with the person asking the question and giving suggestive answers with a very limited number of fixes ("I would strongly advise performing a major revision on your presentation of the proofs"; "two potential problems. One is that you may be in error, [...]. The other is presentation[...]").

If we are attentive enough, we all know well what the source of our problems are: The magic word is feedback. If people complain consistently that our papers are hard to read, the suggestion to work it over has a point. If again and again referees find errors in the manuscript, we will take much more care to avoid errors (proof-read, double-check, triple-check).

But if we get an outlier answer and cannot fathom what exactly should be the problem, it is very, very likely that we are not the source of the problem. Working the paper over in this case is a waste of time.

The reason(s) that a referee rejects a paper are virtually unlimited. He is wrong, she does not care, he is busy, she is right, but explains it badly. Whatever.

But what you can do is to read very carefully the answer and ask yourself under what circumstances a person would give the answer. Is it aggressive, dismissive, bored, sad ? It is rather short or more detailed ? Does it look like the referee invested time or it is hastily written with boilerplate passages ? On this you could often discern what the real reason for the rejection is.

Everyone will sooner or later have a paper rejected for inexplicable reasons, it is normal. Nothing to be afraid of.

That said, the best strategy already mentioned by other answers is to cut the losses and simply go to another journal. I would advise to challenge the decision if and only if the editor made it clear that the decision is not final and then if and only if it is objectively important to have it published in this specific journal. In that case do everything in your ability to check and recheck your paper and hone it to perfection because you will only get exactly one chance to convince the editor.

The reason is that the referee thinks that our results are wrong or trivial.

This first caught my attention. Trivial and wrong are two completely different things. How did you come to that conclusion?

the "errors" pointed out by the referee

This leads me to believe that the issue is mainly about errors. But:

In all modesty, we think that the referee understood very poorly even the statements of our theorems.

has, two possibilities:

• you are right. Math is quite hard and he did not invest enough time to understand it. Or maybe he does not even have the ability to. Which should not be "your" problem.
• He is very good in the field you are working and sees your results really as trivial. He therefore did not read it properly and marked wrong errors (it may looked to him like a "trivial paper with errors"...)

In both cases, I'd really recommend, to

Write an e-mail to the editor explaining why we disagree with the decision?

That's the most "academic" solution in my eyes as problems should be discussed until you agree on the same conclusion (even dough this is surely not possible everywhere, it is in math). Regarding the second case, it is may even possible, that you missed a point. You know, we all make errors all the time. But submitting a paper where someone (who actually should understand the topic) spotted errors and just ignoring (not able to convince him otherwise) his opinion is quite, let's say, self-confident (especially in math), and in general not advised to do;)

Don't get this wrong; most probably you are right and he is wrong. Ok. But you surely don't want it the other way around. Better make sure it is not.

Instead of writing directly to the editor, it is may a good advice to let your paper check by a colleague in your field, who is neither the referee nor the author to check for a third opinion.

Others suggested to rewrite your paper for more comprehensibility. I would not conclude that already; too many other factors may play a role. Depending on the editor's answer (say he did not get the points as he find it confusingly written) I might rewrite the parts.

Another journal is surely a good idea if that somehow won't work out, but I don't think you are in a hurry, right?