Здравствуйте, hyp1k, Вы писали:

H>Ничего страшного, просто меня это удивило. Почему не вызывается изначально первый метод?!

1) Вы не дописали IComparable<Vertex> в заголовке своего класса.
2) Map не использует обобщенную версию интерфейса, а ограничивается только IComparable.