У вас есть два варианта:
(1)
Graph<V extends YourVertexSuperClass, E>
В этом случае я предполагаю, что у вас есть что-то вроде
public interface YourVertexSuperClass { ... }
public class Car implements YourVertexSuperClass { ... }
public class Person implements YourVertexSuperClass { ... }
и т.д.
(Интерфейс может быть абстрактным классом, конечно.)
Возможно, это действительно имеет смысл, только если у ваших типов вершин есть что-то общее.
(2)
Graph<? extends Object, E>
В этом случае вы можете вставить что-нибудь, то есть без ограничений типа.