The nature of the gapless excitations in a quantum many-body system is an emergent property, including underlying order. A simple "classical" example is that the sound waves in crystals result from the breaking of continuous translational symmetry. More profound examples are the Goldstone modes associated with spontaneously broken symmetry and the edge states associated with topological order in fractional quantum Hall states. Furthermore, the presence and gapless character of these excitations are particularly robust against perturbations and variations in microscopic details. This property is dubbed by Laughlin and Pines, a quantum protectorate.
A key property of graphene is the Dirac cone that describes the elementary electronic excitations. This can be "derived" from considering the band structure of a tight-binding model on the honeycomb lattice [a hexagonal lattice with two identical atoms per unit cell]. Hence, one might think that the Dirac cone is "just" a one-electron effect and is not an emergent phenomenon arising from many-particle interactions. I have said and thought that in the past. However, real graphene involves interacting electrons and the presence of disorder and impurities. The Dirac cone is quite robust against these additional interactions.
If the electron-electron interactions were stronger in graphene it would be an insulator. If the interactions were purely short range and described by a Hubbard model, then undoped graphene with a larger lattice constant [and so a larger U/t] would be a Mott insulator, and possibly a spin liquid. In reality there are longer range screened Coulomb interactions. The emergence of the metallic state [and the quantum criticality associated with the Dirac cone] is an extremely subtle and profound question, nicely discussed in a Physics article by Igor Herbut. There is also an intriguing proposal that free standing graphene may be an insulator (Pauling's dream!) because of the reduced screening due to the absence of a substrate.
Aside: somewhat similar issues are associated with the reasons for the validity of a band structure picture for simple metals. This actually arises for the profound reason of Landau's Fermi liquid theory.
The fact that the Dirac cone and metallicity survives the presence of disorder is also a subtle question. In a conventional two-dimensional metal weak localisation leads to an "insulating state" at zero temperature. Graphene is different. There are also interesting questions about the "minimum metallic conductivity" that I need to learn about.
This post was inspired by a nice colloquium that Michael Fuhrer gave at UQ on friday.