Java objects are referenced by pointers, even if it's not visible in the syntax in the same way as in C++. Your Java function doesn't really return a reference (in the C++ sense, not just a synonym for pointer), but it returns a pointer, and that pointer is returned by value. So the equivalent C++ would be something like this:
Vertex* a = graph.addVertex(null);
Vertex* b = graph.addVertex(null);
It is a mistake to think of the "references" in Java as the same thing as the "references" in C++. The Java "references" are pointers. C++ "references" are aliases for variables, which is not the same thing as a pointer, even though they are usually (but not always) implemented "under the hood" using pointers.
To clarify: This is not just terminology nitpicking. Your C++ program will not behave the same as your Java program, if you just translate Java references to C++ references. To make an equivalent C++ program, you need to use pointers.
Vertexclass to store shared pointers to its data, if you don't really care about performance.shared_ptrperformance is pretty good, and usually good enough - especially since the compiler will elide many of the copies.