While the fundamental problem of consensus in distrbuted systems has been studied extensively, this has mostly focused on shared-memory and to a lesser extent on asynchronous message-passing models. However, a natural extension is to consider the case of a asynchronous message-passing model over non-complete graphs. In this paper, we study the problem of binary consensus problem over non-complete graphs using Erdfüs-Rényi and describe an algorithm which not only yields the desired primary result, but also achieves this with the stronger constraint of messages from a given source reaching their respective sinks over k edge-disjoint spanning trees by extending Correia et al.'s variant of Ben-Or's algorithm.