For a short answer: never.

For a longer answer...  It looks like vertices are dynamically allocated and the vertex set (listS, setS, etc.) stores pointers to those vertices. In the case of associate containers, the key_type is just the pionter value. In otherwords, add_vertex will never look for a previous instance of the vertex.