The new AllGraphs command returns an iterator with which one can step through all graphs matching a particular set of criteria, such as vertex count or edge count. It is also possible to cause the Iterator to return only connected graphs or only graphs which are not isomorphic to a graph previously returned by this Iterator.

The new command Condensation computes the condensation of a given (directed) graph.

The condensation of a graph G is a graph C whose vertices correspond to the strongly connected components of G.  The condensation C will have an arc from u to v whenever there is an arc from the strongly connected component of G corresponding to u to the strongly connected component of G corresponding to v.

The new command FindAsteriodalTriple searches for an asteroidal triple in the given graph.  The related new command IsAsteroidalTripleFree returns true when the given graph does not contain an asteroidal triple.

An asteroidal triple for a graph G is a triple $\left(u\,v\,w\right)$ of non-adjacent vertices of G such that for each pair from the triple, there exists a path between them that does not intersect the third vertex or any of its neighbors.

The new command IsArchimedeanGraph tests whether a given graph is an Archimedean graph.

The Archimedean graphs are those graphs which form the skeletons of the Archimedean solids. The Archimedean solids comprise 13 convex polyhedra whose faces are regular polygons and whose vertices are all symmetric to each other, but which are not Platonic solids (polyhedra whose faces are identical).  

The new command IsDominatingSet tests whether a set is a dominating set for a given graph.

A dominating set of a graph G is a subset S of the vertices of G, with the condition that every vertex in G must either be an element of S or the neighbor of an element of S.

The new MinCut command works per the Max-Flow Min-Cut Theorem and uses the flow output to compute a cut-set. The EdgeConnectivity and VertexConnectivity commands have been updated to use MinCut so that they can now also return cut-sets.

The MinCut command will call MaxFlow by default but can reuse the flow matrix if MaxFlow has been called already.

The moral graph of a directed graph G is a graph M with the same vertices as G but with all directed edges made undirected, and with the property that whenever two directed edges in G share a destination vertex, then their source vertices are connected in M.

The new command MoralGraph constructs the moral graph given a directed graph.

The RelationGraph command constructs a graph on a given vertex list in which an edge is present in the graph whenever a particular Boolean predicate on its two vertices is true.

In this example, the neighborhood of the element 5 will be all those vertices whose values are coprime with 5:

The WienerIndex command computes the Wiener index on a given graph. The Wiener index of a graph is the sum of the lengths of the shortest paths between all pairs of vertices in the graph.

The Distance and ShortestPath commands now use the edge weights of a weighted matrix. They both have a new option ignoreweights to compute the distance or shortest path in the underlying unweighted graph.

The MaxFlow command now works on all graphs.  It now treats an unweighted graph as a graph with all edge weights equal to 1, or to the edge multiplicity for multigraphs.

The Archimedean graphs are those graphs which form the skeletons of the Archimedean solids.  The Archimedean solids comprise 13 convex polyhedra whose faces are regular polygons and whose vertices are all symmetric to each other, but which are not Platonic solids (polyhedra whose faces are identical). They were first enumerated by Archimedes.

The new command IsArchimedeanGraph tests whether a given graph is an Archimedean graph.

The following new commands generate each of the Archimedean graphs.

The Möbius ladder graph on $2 n$ vertices may be understood visually as the ladder graph on the same vertices, with the addition of two edges: one connecting the left-hand side of the "op rung to the right-hand side of the bottom rung, and one connecting the right-hand side of the top rung to the left-hand side of the bottom rung.

The Wagner graph is a 3-regular graph which is a particular instance of an Möbius ladder graph on 8 vertices.