Graph recognition by moving agent

A graph recognition problem is considered by means of agent which moves on graph edges, marks on its nodes and incidentors. A recognition method is proposed in which an agent builds not exploring graph. The method requires two different marks and one pebble, and its number of steps is cubic function from number of graph nodes.