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

Cycles and Connectivity

 

ReferenceReference

Graph Cycles

FindCycle find a cycle in a graph

Girth length of the shortest cycle

EulerianCycle find an Eulerian tour on a graph

HamiltonianCycle find a Hamiltonian cycle

ExtractCycles  ▪  EulerianQ  ▪  HamiltonianQ  ▪  AcyclicQ

TravelingSalesman  ▪  TravelingSalesmanBounds  ▪  DeBruijnSequence

Graph Connectivity

ConnectedQ test if a graph has only one component

ConnectedComponents get lists of connected vertices

StronglyConnectedComponents  ▪  WeaklyConnectedComponents

OrientGraph find strongly connected orientation of a graph

ArticulationVertices find cut points of a graph

Bridges find bridges of a graph

BiconnectedComponents  ▪  BiconnectedQ

EdgeConnectivity minimal number of edges that disconnect the graph

VertexConnectivity  ▪  VertexConnectivityGraph