Byzantine Agreement is possible on a network consists of only unicast channels (i.e. a 2-uniform hypergraph) if and only if n > 3t (Pease et. al. [PSL80]). However, Fitzi and Maurer ([FM00]) show that if, in addition to all unicast channels, there exists local broadcast among every three processes in the network (i.e. a complete (2,3)-uniform hypergraph), n>2t is necessary and sufficient for Byzantine agreement. In this paper, we show that optimum tolerance of n>2t can be achieved even if a substantial fraction of the local broadcast channels are not available. Specifically, we model the network as a (2,3)-uniform hypergraph H = (P,E), where P denotes the set of n processes and E is a set of 2-tuples and/or 3-tuples of processes (edges or 3-hyperedges), wherein each 3-hyperedge represents a local broadcast among the three processes; we obtain a characterization of the hypergraphs on which Byzantine agreement is possible. Using this characterization, we show that for n=2t+1, (2/3t^3 + Theta(t^2)) 3-hyperedges are necessary and sufficient to enable Byzantine agreement. This settles an open problem raised by Fitzi and Maurer in [FM00]. An efficient protocol is also given whenever Byzantine agreement is possible.