Well from my understanding, you are sharing the objects between your different objects, i.e. the Graph and Edge objects contain pointers to shared Nodes. In this case, of course storing the objects directly is out of the question, or at least one of the two objects that hold the shared Node, must store it as a pointer, otherwise the instance of Node that is shared will not be the same (i.e. copies of each other).
So you're right to use pointers. But watch out! Typically in a graph architecture, you need to define rules of ownership (i.e. who is responsible for destroying the instance of a Node to which several other objects (Graph, Edge, Node) hold a pointer to). Then, you have to worry about the order of destruction, such that an object which holds a pointer to a Node for which he doesn't have ownership, should not access it after the owner has destroyed it. This can become quite tricky. Then, you have cycles or semi-cycles to worry about as well.
Luckily, Boost Smart Pointers give you a nice trio of smart pointers that can really help in graph-like object hierarchies: shared_ptr, weak_ptr, unique_ptr (all now part of TR1 standard library, i.e. tentative release 1). A shared_ptr is a reference-counted pointer, meaning that it will automatically destroy only when all copies of that shared_ptr are deleted or gone out-of-scope. This can allow you to make sure no pointers to a Node will suddenly point to the freed …