Da muss man ein bisschen aufpassen. Was |V| alleine betrifft: ja. |V| <= |V|*log(|V|), also gilt gesamt O(|V|*log(|V|). In Deinem Beispiel geht es um eine bessere Abschätzung der Laufzeitkomplexität, die von Knoten und Kanten in unterschiedlichem Maße abhängt (in der Regel hat man so etwas bei ausgabesensitiven Algorithmen, d. h. die Laufzeitkomplexität hängt entscheidend von der Zahl der Elemente in der Ausgabe ab). Da macht es natürlich keinen Sinn, die Kanten oder Knoten unter den Tisch fallen zu lassen.
Bei einem allgemeinen Sortieralgorithmus wäre ja O(n log(n)) optimal. Das n bezieht sich hier auf die Zahl der Elemente, die Ausgabe hat auch n Elemente -> alles gut. Beim Suchen des Maximums hätte man dagegen O(n + 1), weil man alle Elemente betrachtet und eines ausgibt. Die 1 ist aber konstant, also fällt die unter den Tisch: O(n), der Algorithmus ist nicht ausgabesensitiv.
Wenn dagegen ein Algorithmus eine vorab nicht bekannte Zahl an Elementen ausgibt und dafür eine Datenstruktur verwenden muss (z. B. ein Baum), dann ist der Algorithmus ausgabesensitiv und man interessiert sich für die Laufzeitkomplexität.