As of Version 10, most of the functionality of the Combinatorica package is built into the Wolfram System. >>

Built-in Graphs

 

ReferenceReference

CompleteGraph a graph with an edge between each pair of vertices

RandomGraph construct a random graph

EmptyGraph  ▪  OddGraph  ▪  CirculantGraph  ▪  CompleteKPartiteGraph  ▪  Turan

Cycle a circular chain of edges

Star a tree-like graph with one vertex connected to all others

GridGraph graph with nodes on a grid

Wheel  ▪  Hypercube  ▪  ButterflyGraph  ▪  ShuffleExchangeGraph  ▪  DeBruijnGraph

Special Graphs

Harary smallest -connected graph with vertices

TutteGraph example of non-Hamiltonian graph

PetersenGraph  ▪  GeneralizedPetersenGraph  ▪  CageGraph

MeredithGraph  ▪  NoPerfectMatchingGraph  ▪  ThomassenGraph

KnightsTourGraph  ▪  ChvatalGraph  ▪  CoxeterGraph  ▪  FolkmanGraph

FranklinGraph  ▪  FruchtGraph  ▪  GrayGraph  ▪  GroetzschGraph

HerschelGraph  ▪  HeawoodGraph  ▪  LeviGraph  ▪  McGeeGraph  ▪  RobertsonGraph

UnitransitiveGraph  ▪  Uniquely3ColorableGraph  ▪  WaltherGraph

CubeConnectedCycle  ▪  MycielskiGraph

Platonic Solids

TetrahedralGraph  ▪  CubicalGraph  ▪  OctahedralGraph

IcosahedralGraph  ▪  DodecahedralGraph