The outage performance of wireless networks with unstructured network topologies is investigated. The network reliability perspective of graph theory is used to obtain the network outage polynomial of generalized wireless networks by enumerating paths and cut-sets of its graph representation for both uncorrelated and correlated wireless channels. A relation is established between the max-flow min-cut theorem and key communication performance indicators. The diversity order is equal to the size of the minimum cut-set between source and destination, and the coding gain is the number of cut-sets with size equal to the minimum cut. An ergodic capacity analysis of networks with arbitrary topologies based on the network outage polynomial is also presented. Numerical results are used to illustrate the technical definitions and verify the derivations.