...but part of the design of the core of the Internet is that it is, in fact, designed to survive a nuclear war.
Which isn't to say you'd have much of the Internet left, but if it wasn't fried by EMP, you could start reconfiguring your routers to connect with surviving nodes.
The backbone of the internet should survive as it was intended, but the more local components (ISPs) would probably fail. Many customers only have 99% or 99.9% uptime, and this is with the power grid working more-or-less correctly.
For this to actually work, we would probably find ourselves switching to a loose-coupled wireless internet (at least for the ISP piece), which is something that has been researched.