Graph Properties

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

Degrees list of degrees of vertices

InDegree number of incoming edges

DegreeSequence list number of edges for each vertex

GraphicQ test if a list of integers is a graphic sequence

OutDegree  ▪  RealizeDegreeSequence  ▪  Spectrum

ListGraphs list of nonisomorphic undirected graphs

NumberOfGraphs number of nonisomorphic undirected graphs with vertices

GraphPolynomial  ▪  NumberOfDirectedGraphs

ListNecklaces list distinct necklaces

NecklacePolynomial  ▪  NumberOfNecklaces

Cycles and Connectivity »

FindCycle find cycle in a graph

HamiltonianCycle find a Hamiltonian cycle

ConnectedComponents get lists of connected components

OrientGraph  ▪  Bridges  ▪  ExtractCycles  ▪  TravelingSalesman  ▪  ...

Graph Coloring

TwoColoring color vertices of a bipartite graph

ChromaticPolynomial compute chromatic polynomial for a graph

ChromaticNumber smallest number of colors to color the graph

MinimumVertexColoring color a graph with the fewest colors

EdgeColoring  ▪  BipartiteQ  ▪  Backtrack

VertexColoring  ▪  BrelazColoring  ▪  EdgeChromaticNumber  ▪  PerfectQ

Graph Predicates

IdenticalQ compare two graphs

IsomorphicQ test if two graphs are isomorphic

PseudographQ test if a graph is a pseudograph

AcyclicQ test if a graph is acyclic

EmptyQ  ▪  CompleteQ  ▪  SimpleQ  ▪  MultipleEdgesQ  ▪  UndirectedQ  ▪  UnweightedQ

PlanarQ  ▪  CliqueQ  ▪  BipartiteQ  ▪  SelfLoopsQ  ▪  TriangleInequalityQ