The district of southern California and Japan are divided into small cubic cells, each of which is regarded as a vertex of a graph if earthquakes occur therein. Two successive earthquakes define an edge and a loop, which replace the complex fault-fault interaction. In this way, the seismic data are mapped to a random graph. It is discovered that an evolving random graph associated with earthquakes behaves as a scale-free network of the Barabasi-Albert type. The distributions of connectivities in the graphs thus constructed are found to decay as a power law, showing a novel feature of earthquake as a complex critical phenomenon. This result can be interpreted in view of the facts that frequency of earthquakes with large values of moment also decays as a power law (the Gutenberg-Richter law) and aftershocks associated with a mainshock tend to return to the locus of the mainshock, contributing to the large degree of connectivity of the vertex of the mainshock. It is also found that the exponent of the distribution of connectivities is characteristic for a plate under investigation.

14 pages, 3 figures, substantial modifications