The energy efficiency (EE) of a multi-user multi-relay system with the maximum diversity network coding (MDNC) is studied. We explicitly find the connection among the outage probability, energy consumption, and EE, and formulate the maximizing EE problem under the outage probability constraint. Relay scheduling (RS) and power allocation (PA) are applied to schedule the relay states (transmitting, sleeping, and so on) and optimize the transmitting power under the practical channel and power consumption models. Since the optimization problem is NP hard, to reduce computational complexity, the outage probability is first tightly approximated to a log-convex form. Furthermore, the EE is converted into a subtractive form based on the fractional programming. Then, a convex mixed-integer nonlinear problem is eventually obtained. With a generalized outer approximation algorithm, RS and PA are solved in an iterative manner. The Pareto-optimal curves between the EE and the target outage probability show the EE gains from PA and RS. Moreover, by comparing with the no network coding (NoNC) scenario, we conclude that with the same number of relays, MDNC can lead to EE gains. However, if RS is implemented, NoNC can outperform MDNC in terms of the EE when more relays are needed in the MDNC scheme.