Steady increases in natural gas transportation volumes have prompted operators to reevaluate the performance of the existing gas-pipeline infrastructure. Conventional wisdom dictates that adding an additional link or a pipe leg in a gas-transportation network should enhance its ability to transport gas. Several decades ago, however, Dietrich Braess challenged this traditional understanding for traffic networks. Braess demonstrated that adding extra capacity could actually lead to reduced network efficiency, congestion, and increased travel times for all drivers in the network (the so-called "Braess paradox"). The study of such counterintuitive effects, and the quantification of their impact, becomes a significant priority when a comprehensive optimization of the transportation capacity of operating gas-network infrastructures is undertaken.