Abstract: This paper proposes a network code construction method which has low decoding delay. The key idea of this method is that, among all the disjoint paths from the source to a destination, one path is selected as “convenient path”, on which packets are delivered directly without coding. Allocating maximum number of convenient paths for all the destinations in a multicast network can be modeled as the problem of maximal complete sub-graph. Both theoretical analysis and numerical results from example networks show that the proposed network code construction method can reduce the decoding delay effectively without any reduction in throughput benefit of network coding. The method introduced by this paper can serve as an efficient way for transmitting data of delay sensitive applications such as media streaming.