This paper investigates the performance of an underlay cognitive relay system where secondary users(SUs) suffer from a primary outage probability constraint and spectrum-sharing interference imposed by a primary user(PU). In particular, we consider a secondary multi-relay network operating in the selection decode-and-forward(SDF) mode and propose a best-relay selection criterion which takes into account the spectrum-sharing constraint and interference. Based on these assumptions, the closed-form expression of the outage probability of secondary transmissions is derived. We find that a floor of the outage probability occurs in high signal-to-noise ratio(SNR) regions due to the joint effect of the constraint and the interference from the PU. In addition, we propose a generalized definition of the diversity gain for such systems and show that a full diversity order is achieved. Simulation results verify our theoretical solutions. This paper investigates the performance of an underlay cognitive relay system where secondary users (SUs) suffer from a primary outage probability constraint and spectrum-sharing interference imposed by a primary user (PU). In particular, we consider a secondary multi-relay network operating in the selection decode-and-forward (SDF) mode and propose a best-relay selection criterion which takes into account the spectrum-sharing constraint and interference. Based on these assumptions, the closed-form expression of the outage probability of secondary transmissions is derived. We find that a floor of the outage probability occurs in high signal-to-noise ratio (SNR) regions due to the joint effect of the constraint and the interference from the PU. gain for such systems and show that a full diversity order is achieved. Simulation results verify our theoretical solutions.