  One of the important unsolved problems in information theory is the
conjecture that network coding has no rate benefit over routing in undirected
unicast networks. Three known bounds on the symmetric rate in undirected
unicast information networks are the sparsest cut, the LP bound and the
partition bound. In this paper, we present three results on the partition
bound. We show that the decision version problem of computing the partition
bound is NP-complete. We give complete proofs of optimal routing schemes for
two classes of networks that attain the partition bound. Recently, the
conjecture was proved for a new class of networks and it was shown that all the
network instances for which the conjecture is proved previously are elements of
this class. We show the existence of a network for which the partition bound is
tight, achievable by routing and is not an element of this new class of
networks.
