How to optimize graphene geometry with Gaussian?
The decision for a bond to be visually represented as a single, double, or triple bond in a molecular visualization program (e.g. GaussView) is based on rather arbitrary distance rules that often do not represent the actual bond order. Unless you are investigating the bond order in other ways (e.g. Wiberg bond index), what you're seeing for the bond order is nothing more than a guess. If you switch visualization programs, you'll likely find the bond orders to change.

If, indeed, the actual geometry of the graphene is completely unphysical after the geometry optimization, here are some questions to ask yourself:


How good is the initial structure you gave the optimization algorithm? Are you using a template graphene structure that should be close to the final geometry? If you made it "from scratch", it would be worthwhile to apply symmetry to your structure prior to running the calculation in Gaussian.
How have you terminated your graphene? You say you're using Gaussian, so I doubt you are using periodic methods. Have you terminated all dangling bonds with hydrogens, for instance? 
In line with Point #2, what is the size of your graphene "cluster" model? Perhaps the cluster you chose is too small.
Ensure you don't have various input file errors (e.g charge/multiplicity).