Nous montrons que dans la classe des graphes connexes tels ;lue deux a&es incidentes quelconques appartiennent a un et un seul quadrilatere, les hypercrtbes finis sont les graphes de degre minimum n lini et possedant 2" sommets.
The fol!owing theorem' is proved: Let % be the class of connected graphs such that ea .h pair of distinct adjacent edges lies in exactly one 4-cycle. Then G in %Z is a finite hypercube 15 the minimum degree 6 of G is finite and* IV(G)1 = 2".
By a 4-cycle we mean a set of 4 edges, each of them being adjacent with two others; a finite hypercube or a n-cube is defined to be the graph Cn with V(C, ) = (0, 1)" and where x and y are joined iff the n-tuples x and y differ in exactly one position3; the distance d(x, y) between 2 vertices in a connected graph G is the minimum number of edges in a path joining x: to y.
. The 6 smallest graphs in % are shown in Fig. 1.
. Every G in % is a simple graph (i.e. a graph without loops or multiple edge?;) unless G itself is a loop. ' After the first version or this paper was *written a book by -~~~d~~r 161 was published. similar result but with different approach and proofs may be fourd. * VI G) denotes the vertex set of graph G. For any X, 1x1 denotes the cardinal (number of elements) of X. ' C, can also be obtained from (7, = e following induction Cn+, = (1, + & If~r the n Ition of the Cartesian sum of two graphs see for example [a]).