They both could be correct, but they have very different meanings. To "give up" John means to discharge him, or to no longer use his services, or to let him go.
John has been a wonderful butler, but since we lost our money in the stock market crash, we can no longer afford to have servants. I am afraid that we have to give up John, as well as the maid, the cook and the gardener.
To "give up on John" means that one can no longer base any hopes or expectations on John.
I had wanted all of my students to become great acrobats, but after seeing how clumsy your son is, I am afraid we have to give up on John.
I know that you want to believe that your husband John survived the sinking of the Titanic, but after all these years I'm afraid we have to give up on John.
Honey, while I know you think John would make a perfect husband, you have to face facts and realize that he is gay and will never ask you to marry him. I'm afraid we have to give up on John.