Structural learning, in which the structure of estimation systems are optimized, has been actively studied in researches on supervised learning of fuzzy rules and neural networks. The GAd (Genetic Algorithm with Degeneration) is one of the structural learning methods, which is modeled on genetic damage and degeneration. In GAd, degeneration pressure must be controlled properly to get the better structure of the estimation systems. But it is difficult to tune the degeneration pressure manually. In this paper, the idea of coevolution is introduced into GAd and a Coevolutionary Genetic Algorithm with Degeneration (CGAd) is proposed to control the degeneration pressure adaptively. Coevolution is an evolution model, where two types of individuals evolve cooperatively or competitively each other. In CGAd, the learning individuals that learn the estimation systems and the control individuals that control the degeneration of the learning individuals evolve cooperatively. To show the advantage of CGAd, it is applied to the structural learning of neural networks. It is shown that CGAd can find better structures than GAd.