In this paper, we consider a problem on the reachability of a version of graph-rewriting system. It deals with 3-regular graphs with states for the vertices. They differ from ordinary graphs so that a cyclic order of the edges is assigned on each vertex. Graphs are rewritten with a rule set of graph rewriting. For any two such connected graphs with at least four vertices of distinct states, we show that there exists a rule set that rewrites one to the other. (C) 2009 Elsevier B.V. All rights reserved.