Build algorithm to determine if a graph is created with a given algorithm

Let: G - the graph V(G) - the vertices E(G) - the edges v,w particular vertices.

the algorithm for building the graph:

//adding v (a new vertex to the graph)
if v has a friend in V (G) then E ← E ∪ {vw|w ∈ V (G)}
G ← (V ∪ v,E)

Can you please give me at least a clue how could I find out if a given graph was built with this algorithm ?

Thank you in advan开发者_开发知识库ce.

If G has vertices with degree 0, they must have been added after the last "friendly" vertex was added. Remove them. Once we're finished culling the friendless, there must be a "last friendly vertex added," identifiable because it's attached to everything. Find it, remove it, and return to seek-and-destroy-friendless. If the graph is eventually completely destroyed by this process, it can be created by your algorithm.

It's pretty much saying, when you add v to the graph, if it has any friends in thew graph, then it gets an edge to all existing vertices. So every addition either adds no edges, or edges to all vertices.

The tricky thing is that a vertex added without any friends may still get an edge from a subsequent added vertex. If you can tell which order they were added in, then you could determine whether the graph is possible by replaying that order and checking that every addition adds either 0 or all possible edges.

If you don't know the order, you could try "unwrapping" the graph by removing the most recent vertices, if you can figure them out.

Edit suggested algorithm removed because it's homework ;-).