Network connectivity under node failure

•A model of network formation with the possibility of node failure has been analysed.•Players receive benefits from connecting directly and indirectly through costly links.•Conditions are identified for Nash and efficient networks.•The conditions involve notion of k-Node Super Connectivity.

We examine a non-cooperative model of network formation where players may stop functioning. We identify conditions under which Nash and efficient networks will remain connected after the loss of k nodes by introducing the notion of k-Node Super Connectivity.