Can I draw a graph whose vertices have two kind of labels?

edit

Unfortunately, there is no way to define non-injective labeling for vertices of Sage graphs as there is a confusion between the vertices themselves and possible labels on them, see the documentation.

For example:

sage: G.relabel(V)
NotImplementedError: Non injective relabeling

There are two possible workarounds. You can make the pseudo-labelling injective as follows:

sage: G.relabel(list(enumerate(V)))
sage: G.vertices()
[(0, 'Dog'), (1, 'Dog'), (2, 'Cat'), (3, 'Cat')]
sage: G.plot()

You can also use colors during the plot to pseudo-label the vertices:

sage: G.plot(partition=[[1,2],[3,4]])
sage: G.plot(partition=[[1,2],[3,4]], vertex_labels=False)