This paper models the evolution of network structure (connectivity) and design (flight frequency, aircraft size, prices) in the post-deregulation U.S. airline industry. We show that legacy carriers choice of Hub-and-Spoke networks and the emergence of low cost carriers (LCCs) operating Point-to-Point networks were optimal network choices. We demonstrate that LCCs need not necessarily charge lower prices and their entry impacted legacy carriers' prices in all markets even those where there is no direct competition. We show that in response to entry, legacy carriers optimally lower flight frequency, leading to longer wait times between flights for which passengers are compensated by lower prices. Conversely, if the entrant later exits, legacy carriers raise flight frequency and therefore prices, which may erroneously appear to be predatory pricing when in fact it is the consequence of optimal network redesign. Finally, we demonstrate that even though low cost carriers lower prices, total social welfare with competing network structures can also be lowered. We argue that social welfare may have been, and still can be, higher if entry and exit in air passenger travel industry is regulated.