Graph Properties

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

• Displaying Graphs
• Constructing Graphs