I have an undirected graph which grew according to a recursive algorithm, i.e., it started with a single vertex and then, one after another, new vertices arrived and connected to existing ones.
Now, I'm given the graph with, say, $n$ vertices. I would like to determine (efficiently) which vertex was the first one. How can I do so?
I am already aware of an algorithm by Shah & Zaman (2011) from this paper. However in this paper, they assume that the graph of interest (in their case the rumor graph) is actually a tree. In my situation, this does not necessarily have to be true.