The application of device-to-device (D2D) communication in cellular networks can significantly improve the efficiency of spectrum utilization, which benefits local area cooperative services. On the other hand, network coding can realize more efficient cooperation among cellular users. Thus, it is natural to combine network coding with D2D communication in order to further increase the system sum rate. In this paper, a coalitional graph game framework is proposed to jointly accomplish resource allocation and relay selection, two challenging problems in network coding-aided D2D communication networks. It is shown that this framework can model D2D communication combined with various network coding schemes. Based on the coalitional graph game framework, a distributed algorithm with low computational complexity is proposed to solve the formulated problem for physical layer network coding-aided D2D communication. Finally, the performance of the proposed transmission scheme is evaluated through extensive simulations.