Deleting what wasn't allocated with new using pointers

Today, I have faced the hardest problem in my programming career Ever, So I hope someone can help.

In graph_p.h I have:

typedef struct Graph* Graph_P;

(Graph_P is a pointer for a Graph)

While Graph Is another class which I defined

In graph_p.cpp I have the following functions:

Graph_P create()
{
    try {
        Graph_P graph=new Graph;
        return graph;
    }
    catch (std::bad_alloc &) {
        std::cout << "Error: Allocation Failed" << std::endl;
        return nullptr;
    }
}

void destroy(Graph_P graph_p)
{
    delete graph_p;
}

And the following graphUnion function (which is our topic):

Graph_P graphUnion(Graph_P graph_in1, Graph_P graph_in2, Graph_P graph_out) {
    try {
        *graph_out=(*graph_in1)+(*graph_in2);
//I have defined operator + between two graphs which returns a new graph built using default c'tor **not using new**

        destroy(graph_out);
        return graph_out;
    }
    catch (CException::exception &e) {
        std::cout << e.what() << std::endl;
        return nullptr;
    }
}

What's the problem?

In case operator + failed I'm deleting the content of graph_out which shouldn't be done.

Suggested Solution:

Saving graph_out content in a temporary Graph_P object like this:

Graph_P graphUnion(Graph_P graph_in1, Graph_P graph_in2, Graph_P graph_out) {
    try {
        Graph tmp=*graph_out;
        tmp=(*graph_in1)+(*graph_in2);
        destroy(graph_out);
        graph_out=&tmp;
        return graph_out;
    }
    catch (CException::exception &e) {
        std::cout << e.what() << std::endl;
        return nullptr;
    }
} 

What's the problem?

I am putting a value inside graph_out that wasn't allocated via new so if the user types destroy(graph_out) outside the function, that would be an undefined action since I read:

You need to delete only what you newed

How may I fix this?