In [5, 61 a criterion for the undecidability of second order theories of classes of graphs is introduced. This criterion leads to a "measure of complexity" of a class of graphs. In this note we introduce some graph theoretical operations and prove that the class of all graphs which have the smallest "degree of complexity" can be built up by this operations. As a consequence, we get the decidability of the monadic second order theory of this class of graphs.
In this note, i, j, k, I, m and n denote natural numbers and w denotes the set of all natural numbers. We suppose that each natural number is the set of all natural numbers smaller than it ( n = { i / i -c n } ) . Thus, 0 denotes the empty set.
By X , U , n, \ we mean the usual set theoretical operations. For any set A , 2 will denote t h e cardinality of A . Relational structures ( A , R), where A is a non-empty set and R a binary relation over A , will be called graphs. Mainly we will restrict our attention to finite, irreflexive and symmetric structures. For a graph @ = ( A , R) we define 1 6 1 = df A and Ra = df R. Any graph @ for which Ra = 0 will be called trivial. We shall write ( A , R)-=(B, S) if and only if there exists a subset C of B for which (C, SIC) (SIC denotes the restriction of the relation S to C (Sn(CxC))) is isomorphic to ( A , R).
For any graph ( A , R), let P , ( ( A ,R)) be the class of graphs ( B , S> such that there exist a,, b , c with aEA, bEA, c e A , ( a , b)ER, B = A U { c } andS=(R((a, b ) , ( b , a)})U { ( a , c), (c, a ) , (c, b ) , (b, c)} . P,((A, R)) let be the class of graphs ( B , S) s.t. there exist a , b, c with uCA, bCA, cEA, u + c , (u, b)ER, (b, c)ER, b has valency 2 , B=A{b} and S = (RIB)U { ( a , c ) , ( c , a ) } . Now let P,((A,R)) be the class of graphs ( B , S) s.t. there exists an aEA with B=A{u} and S= RIB.
For any two graphs ( A , R) and ( B , S ) let P4((A, R), ( B , S ) ) be the class of graphs ( C , T) s.t. there are graphs @' and 0" with @ ' z ( A , R), @ " z ( B , S ) and /@'lnI@''l={u} for some a and C=lO'IUl@"l and T=R,.UR, ... Let P5((A, R), (B, S ) ) be the class of graphs (C, 5") s.t. there are graphs @'