In Sage, the vertices of a graph must be hashable. You can test if this holds by applying the function hash() to whatever you propose to use as a vertex. If it is not hashable you'll get an error message informing you of the fact, if it is hashable you'll get back an integer.
Occasionally the experimental approach to determining hashability will be unsatisfactory, so I offer some comments.
The output of vector() and matrix() is not hashable, but can be made so by using a.set_immutable() (where a may be a matrix or a vector). Subspaces of vector spaces over finite fields are hashable.
Sage has two classes of sets: set() constructs the Python version and Set() the Sage version. Sage Sets are hashable, Python sets are not. The available operations differ (go figure).
If vset is a list of things you want to use as vertices, and they are not readily converted to something hashable, you can construct a graph as follows:
G = Graph( [[1..len(vset)], lambda i,j: adj_pred( vset[i],vset[j])])
Here adj_pred takes two elements of vset and returns True or False according as its two arguments are adjacent or not.
Note that many graph operations will go faster when the vertices are integers, and we can always arrange this after the fact by using G.relabel().