Spectrum allocation in cognitive wireless communication is an important research axis and aims at reforming the existing fixed spectrum allocation policy and improving spectrum efficiency. Satellite communication is faced with the same problem of spectrum underutilization. In this paper we propose a cognitive satellite communication network, which contains satellite section and terrestrial section, as a succinct model to research. Due to the concern for spectrum efficiency and allocation fairness, graph theory algorithm is proposed to be used in satellite communication by imitating traditional terrestrial cognitive networks. In this context, we mainly simulate greedy algorithm and fair algorithm in different conditions and numerical results illustrate the advantages of using graph theory in cognitive spectrum allocation of satellite networks. Furthermore, we also put forward some research directions based on graph theory in the cognitive satellite communication networks.