Math 455.1  • 9 April 2009

A guide to graph-theoretic functions 
in the Combinatorica package

Version 7.00 (for Mathematica 6 and 7)

Copyright © 2009 by Murray Eisenberg.  All rights reserved.

Initialization

The following cell loads the Combinatorica package.

Needs["Combinatorica`"]

Utility functions

The following three functions, provided by Carl Woll of Wolfram Research, are used for working with Combinatorica Graph objects yet using with Mathematica Version 6 rule-list types of graphs. Their use is explained in the subsections "Converting between rule-list graphs and Combinatorica Graph objects" and "Labeling and styling edges with GraphPlot" of the section "Displaying graphs with GraphPlot".

RuleListFromGraph[Graph[edges_,vertices_,___]]:=Module[{vrules},vrules=DeleteCases[Thread[Range[Length[vertices]]->(VertexLabel/.vertices[[All,2;;]])],_->VertexLabel];
Replace[Transpose[{Rule@@@(edges[[All,1]]/.vrules),EdgeLabel/.edges[[All,2;;]]}],{a_,EdgeLabel}->a,{1}]]

GetVertexCoordinates[Graph[edges_,vertices_,___]]:=vertices[[All,1]]

StripVertexCoordinates[g_Graph]:=Replace[First@g,{{a_,b_},opts___}:>(If[MatchQ[#,EdgeLabel],a->b,{a->b,#}]&[EdgeLabel/.{opts}]),{1}];

Purpose of this notebook

This notebook is not really about graph theory!  Rather, it is intended primarily as an extended reference about how to use some of the graph-theoretic functions in the Combinatorica package that ships as part of Mathematica.

The Combinatorica package and its documentation

The Combinatorica package defines of a host of specialized functions for doing discrete mathematics, including graph theory and combinatorics.  We shall be using the package in the rest of this course.

The Documentation Center includes various types of documentation about the packages:

	• a long MouseOver on the whole package;


	• guide pages about the main topics in the package—for example, the guide page about 
MouseOver; and


	• an individual reference page about each function, option, and other name defined in the package—for example, the reference page about the function MouseOver that displays graphs.

If you decide use the kernel function GraphPlot to display graphs instead of the Combinatorica function ShowGraph, then you will also want to consult:

	• the MouseOver reference page; and

	• the  tutorials about MouseOver and MouseOver.

You should navigate through the Documentation Center for relevant information in the usual way.

Creating graphs

The Combinatorica package establishes a new type of Mathematica data type, namely, certain expressions whose Head is Graph.  There are several ways of creating objects of this type.  Once you have created such an object, you may view a representation of it by using the Combinatorica function ShowGraph.or, for more sophisticated control over the result, the Mathematica kernel function GraphPlot.

For creating directed graphs (digraphs), see the section Working with digraphs, below.

Method 1:  Use a Combinatorica function directly to create special types 
of graphs

Cycle graphs

In a cycle graph on a given set of vertices, one arranges the vertices in some order and then connects each vertex in turn by an edge to the next vertex and then connects the last vertex to the initial vertex.

(Subscript[C, 3])=Cycle[3]

Notice that Mathematica does not show you the actual internal object representing this graph!  It just tells you that it's something that has the form Graph[…] .  The first 3 refers to the number of vertices and the second 3 to the number of edges.  What you don't see is the data that describes which vertices are adjacent to which other vertices, that is, which edges join which vertices.  The "Undirected" means that this is an ordinary graph where there is no preferred "direction" along an edge from one of its vertices to the other.

To see which vertices are adjacent to which others, use ToAdjacencyLists.

ToAdjacencyLists[(Subscript[C, 3])]

The result means that for the three vertices, numbered 1, 2, 3, there is an edge joining vertices 2 and 3, an edge joining vertices 1 and 3, and an edge joining vertices 1 and 2.

To display a visual representation of the graph, use the Combinatorica function ShowGraph. (For more sophisticated control over the display, you may instead use the Mathematica kernel function GraphPlot.)

ShowGraph[(Subscript[C, 3])]

Including the options VertexNumber->True or EdgeLabel->True causes ShowGraph to number the vertices or to label the edges, respectively (or both).

ShowGraph[(Subscript[C, 3]),VertexNumber->True,EdgeLabel->True]

By using the Mathematica Style function, you can readily change the appearance of vertex or edge labels.  Note that you need to use the option VertexLabel instead of VertexNumber to do that in the case of the vertices.

ShowGraph[(Subscript[C, 3]),
VertexLabel->(Style[#,FontSize->20,FontColor->Green]&)/@{"1","2","3"},
EdgeLabel->(Style[#,FontSize->20,FontColor->Red,FontSlant->"Italic"]&)/@{"a","b","c"}]

If all you want to do is use the same format for the vertex numbers or labels and edge labels, instead of using Style you may use the ShowGraph option BaseStyle.

ShowGraph[(Subscript[C, 3]),VertexNumber->True,EdgeLabel->{"(Subscript[e, 1])","(Subscript[e, 2])","(Subscript[e, 3])"},BaseStyle->{FontSize->18,FontWeight->"Bold",FontFamily->"Helvetica"}]

For more about labeling and drawing graphs, see section Displaying Graphs.

Complete graphs and complete bipartite graphs

In a complete graph on a given set of vertices, each vertex is adjacent to every other vertex.

(Subscript[K, 4]) = CompleteGraph[4]
ShowGraph[(Subscript[K, 4])]

ShowGraph[(Subscript[K, 4]),
VertexLabel->{"(Subscript[v, 1])","(Subscript[v, 2])","(Subscript[v, 3])","(Subscript[v, 4])"},
EdgeLabel->{"a","b","c","d","e","f"},BaseStyle->{FontSize->18,FontWeight->"Bold",FontFamily->"Helvetica"}]

The labels on the horizontal and vertical edges above appear on top of one another.  In order to separate them, first "shake" the graph—move the vertices random distances up to a specified distance.  Since the shaking is random, you may have to try several times to get satisfactory results.

k4shaken = ShakeGraph[(Subscript[K, 4]),0.4];
ShowGraph[k4shaken,
VertexLabel->{"(Subscript[v, 1])","(Subscript[v, 2])","(Subscript[v, 3])","(Subscript[v, 4])"},
EdgeLabel->{"a","b","c","d","e","f"},BaseStyle->{FontSize->18,FontWeight->"Bold",FontFamily->"Helvetica"}]

For a "bipartite" complete graph you first partition the set of vertices into two disjoint subsets; they you join each vertex in one of those subsets to each vertex in the other subset.

ShowGraph[CompleteGraph[2,3]]

Wheels and stars

ShowGraph[Wheel[5]]

s = Star[4]
ShowGraph[s]

Seeing that Star has a red syntax coloring above, you might think that Mathematica doesn't know about this symbol and hence that you typed something wrong. You would be mistaken! The problem is that there is a meaning assigned to Star by the kernel before the Combinatorica package is ever loaded, and that meaning is currently "shadowed" by the actual function being used, Combinatorica`Star , which when used in that full form, is not colored red.

Empty (null) graphs

(Subscript[N, 5])=EmptyGraph[5]
ShowGraph[(Subscript[N, 5])]

Path graphs

ShowGraph[Path[5]]

(Hyper)cube graphs

(Subscript[Q, 2])=Hypercube[2]

ShowGraph/@{Hypercube[2],Hypercube[3],Hypercube[4]}

Grid graphs

ShowGraph[GridGraph[4, 3]]

Regular graphs

The first argument of RegularGraph is the degree at each vertex; the second argument is the number of vertices.

ShowGraph[RegularGraph[3,4]]

ShowGraph[RegularGraph[2,4]]

Method 2:  Use a Combinatorica function to derive a new graph from old graphs

Union of graphs

The union of two graphs is the new graph whose set of vertices is the union of disjoint copies of the sets of vertices of the two graphs and whose set of edges is the union of the sets of edges of the two graphs.

g2=GraphUnion[Cycle[3],Cycle[4]]
ShowGraph[g2]

Product of graphs

The product of two graphs is the new graph whose set of vertices is the cartesian produce of the sets of vertices of the two graphs and whose set of edges consists of all the edges of each "copy" of each graph.

GraphProduct[Cycle[3], Path[2]]//ShowGraph

Join of graphs

The join of two graphs is the new graph whose set of vertices is the union of disjoint copies of the sets of vertices of the two graphs and whose set of edges consists of all the edges of each of the original graphs together with an edge joining each vertex of the first graph to each vertex of the second graph.

GraphJoin[Cycle[3],Path[2]]//ShowGraph

GraphJoin[EmptyGraph[5],EmptyGraph[1]]//ShowGraph

Subgraph of a graph

For a subset of the set of vertices of a given graph, the induced subgraph has as its set of vertices that subset and as its set of edges all the edges of the original graph that join vertices in the subset.  For example:

g =CompleteGraph[5];ShowGraph[g,VertexNumber->True]

ShowGraph[InduceSubgraph[g,{2,3,4,5}],VertexLabel->{2,3,4,5}]

Notice the use of the VertexLabel option in the preceding example to label the vertices.  The reason for using VertexLabel instead of VertexNumber in this example is to preserve in the display the original vertex numbers.

To create more general subgraphs, in which additional edges are removed, use RemoveEdge or RemoveEdges.

Method 3: Use the Combinatorica function FromOrderedPairs

The first argument to FromOrderedPairs is a list of pairs of vertices that are to constitute the edges.  By default the resulting graph is directed, so for an undirected graph you must explicitly include the option Type -> Undirected.  For example:

g=FromOrderedPairs[{{1,2},{1,3},{2,4}},Type->Undirected]; ShowGraph[g,VertexNumber->True]

To include a loop at a vertex v, just include {v, v} as one of the list items that designates the edges:

g=FromOrderedPairs[{{1,2},{1,3},{2,2},{2,4}},Type->Undirected]; ShowGraph[g,VertexNumber ->True]

To include multiple edges in a graph constructed by using FromOrderedPairs, use AddEdge or AddEdges.

Method 4:  Use the Combinatorica function MakeGraph to prescribe the 
vertices and edges

The function MakeGraph takes two arguments.  The first argument is a list of vertices.  The  items of this list of vertices can be any symbols, numbers, points, etc.   Thus such lists as {v1, v2, v3, v4} or {a, b, c, d} or {1, 2, 3, 4} or {{0,  0}, {1, 0}, {1, 1}, {0, 1}} could be used.

The second argument of MakeGraph is a "vertex-adjacency relation"—a two-argument function that has value True at each pair of vertices that are to be adjacent, that is, to have an  edge connecting them.  For example:

Clear[v1,v2,v3,v4,myEdgeRelation]
myEdgeRelation[v1,v3]=True;
myEdgeRelation[v2,v4]=True;
myEdgeRelation[v1,v4]=True;
MakeGraph[{v1,v2,v3,v4},myEdgeRelation]
ShowGraph[%]

As you can see, by default the function MakeGraph produces a directed graph, in which each edge has a direction.  To make  an undirected graph, supply the option Type->Undirected as an additional argument to MakeGraph.  For example:

Clear[v1,v2,v3,v4,myEdgeRelation]
myEdgeRelation[v1,v3]=True;
myEdgeRelation[v2,v4]=True;
myEdgeRelation[v1,v4]=True;
myEdgeRelation[v3,v3]=True;
MakeGraph[{v1,v2,v3,v4},myEdgeRelation,Type->Undirected]
ShowGraph[%,VertexNumber->True]

Notice the loop at vertex 3 above; it was created because of the specification myEdgeRelation[v3, v3] = True.

MakeGraph[Range[7],(Mod[#,2]==0)&, Type->Undirected]//ShowGraph[#,VertexNumber->True]&

Notice the use of a pure function in the preceding example.  The pure function there is: (Mod[#,2]==0)&. For more about pure functions, see the Mathematica Questions and Answers page on the Math 455 web site.

To include multiple edges in a graph constructed by using MakeGraph, use AddEdge or AddEdges.

Method 5:  Add vertices or edges to, or remove them from, an existing graph

New, isolated (that is, degree 0) vertices may be added to a graph by using AddVertex or AddVertices.

g=Cycle[4];ShowGraph[AddVertex[g]]

Notice that AddVertex—and the Add... and Delete... functions considered here—do not themselves change the value of the graph supplied as argument.  They merely return a new graph.  For example:

g=Cycle[4];AddVertex[Cycle[4]]//ShowGraph
g//ShowGraph

In order to change the value of the graph used as argument, you must make an explicit assignment, using =.  For example:

g =Cycle[4];g=AddVertex[g];ShowGraph[g]

The function AddVertices adjoins the specified number of vertices:

ShowGraph[AddVertices[Wheel[4], 2]]

The remaining functions considered here—AddEdge, AddEdges, RemoveEdge, RemoveEdges, RemoveVertex, RemoveVertices—all refer to edges or vertices of the affected graph by their numbering as shown by the VertexNumber->True option in ShowGraph.  So before using any of these functions to create a new graph, you will usually first want to display the original graph with that option set.

The function AddEdge inserts one additional edge, whose vertices are the ones specified by the second argument; AddEdges inserts one or more edges whose vertices are specified in the second argument.

g =Star[4];
gnew=AddEdge[g,{1,2}];
{ShowGraph[g,VertexNumber->True],ShowGraph[gnew,VertexNumber->True]}

ShowGraph[AddEdges[Star[4],{{1,2},{1,3}}],VertexNumber->True]

Some of the earlier methods for creating graphs allow loops in a graph.  None of the methods allow multiple edges, however.  To create multiple edges, use AddEdge or AddEdges.  For example:

g=Cycle[3];ShowGraph[g,VertexNumber->True]

g=AddEdge[g,{1,3}];ShowGraph[g,VertexNumber->True]

g=AddEdges[g,{{1,2},{1,2}}]; ShowGraph[g,VertexNumber->True]

The AddEdge function also allows adding a loop.  For example:

g=AddEdge[Cycle[3],{3,3}];ShowGraph[g,VertexNumber->True]

The functions DeleteEdge and DeleteEdges remove the specified edge or edges without removing their ends.

ShowGraph[Wheel[4],VertexNumber ->True]
ShowGraph[DeleteEdge[Wheel[4],{1,3}],VertexNumber ->True]

The functions DeleteVertex and DeleteVertices remove the specified vertex or vertices along with all edges having those vertices as ends:

ShowGraph[Wheel[4],VertexNumber ->True]
ShowGraph[DeleteVertex[Wheel[4],2],VertexNumber ->True]

To remove an edge from a graph and at the same time make the ends of that edge into a single vertex, use Contract:

g=GraphUnion[Cycle[3],Cycle[3]];
g=AddEdge[g,{3,6}]; ShowGraph[g,VertexNumber->True]

ShowGraph[Contract[g,{3,6}]]

Method 6:  Directly create a Graph[...] object

The Graph function and Graph[...] objects

To understand the function Graph, look at the InputForm of a graph created by one of the other methods.  For example, use FromOrderedPairs and AddEdge first to create a graph with 4 vertices that includes a loop and a multiple edge:

g=FromOrderedPairs[{{1,2},{1,4},{2,3},{3,4},{1,3},{4,4}},Type->Undirected];
g=AddEdge[g,{1,2}];
ShowGraph[g,VertexNumber-> True]

To see how Mathematica actually represents this graph, look at its InputForm:

InputForm[g]

The InputForm of a graph created by any method is what you would need to type in order to use directly the Graph function from Combinatorica to create the same object.

The InputForm of a Graph expression has two arguments.  The second argument is a list whose items represent the vertices of the graph.  Each item in the second argument is a list having as sole member a list of two coordinates of a point in the plane.  These points in the plane are the locations of the vertices as displayed by ShowGraph.

In the example above, the second argument to Graph is the list:

Last[%]

The first two items of this list are
	{{0,1.}} and {{-1.,0}}
which represent the points (0, 1) and (-1, 0), respectively.

The first argument of the InputForm of a Graph expression is a list whose items specify the edges of the graph.  Mentally number the successive items of the second argument (specifying the vertices) by 1, 2, ….  Then each item of the first argument is a list having as sole member a list of two (not necessarily distinct) numbers that indicate which vertices the corresponding edge has as ends.

In the example above, the first argument to Graph is the list:

First[%%]

The first item of this list is:
	{{1,2}}
This indicates that there is an edge whose ends are vertices number 1 and 2—the vertices specified in the second argument of Graph by {{0,1.}} and {{-1.,0}} , in other words, the vertices represented by the points (0, 1) and (-1, 0).
Since the graph in this example has two edges with ends vertices number 1 and 2, the item {{1,2}} appears twice in the first argument of Graph.  Since there is a loop at vertex number 4, the item {{4,4}} appears in the first argument of Graph.

Why, in a Graph expression, is each list representing an edge, and each list representing a vertex, nested inside a one-item list?  The reason is to allow various options to be included right with each edge or vertex.

To construct a graph by using Graph

To construct a graph by using Graph, just use the form described above.  For example:

myG=Graph[{{{1,2}},{{2,3}}},{{{0,0}},{{1,0}},{{1,1}}}]
ShowGraph[myG,VertexNumber->True]

Vertices and edges of a Graph[...] object

To find the vertices or edges of a Graph object, use the Vertices or Edges function, respectively:

Vertices[myG]

Edges[myG]

These two functions work with any Graph object, however created.  For example:

Vertices[CompleteGraph[3]]

Edges[CompleteGraph[3]]

Method 7:  Use the Combinatorica function RandomGraph or RandomTree

For purposes of experimentation, especially, you may want to create "arbitrary" graphs, that is, graphs not of any specific nature.  One way to do so is to use the Combinatorica function RandomGraph.  For a positive integer n and a number p between 0 and 1, the expression RandomGraph[n,p] returns a graph with exactly n vertices in which approximately 100p% of pairs of vertices are adjacent.

RandomGraph[6,0.3]//ShowGraph

Repeatedly invoking RandomGraph with the same arguments may produce different graphs.

RandomGraph[6,0.3]//ShowGraph

Increasing the second argument to RandomGraph of course increases the probability of a larger number of edges:

RandomGraph[6, 0.7]//ShowGraph

The special Combinatorica function RandomTree creates random trees.

RandomTree[10]//ShowGraph

RandomTree[10]//ShowGraph

Method 8:  Use the Combinatorica function FromAdjacencyMatrix

Method 9:  Use Levon Lloyd's Combinatorica graph editor

Combinatorica includes functions such as CompleteGraph, for creating some common types  of graphs: complete graphs, cycles, etc.  An easy, visual way to create your own graphs is by using the interactive Combinatorica graph editor written by Levon Lloyd.  It is  available at:
	http://www.cs.sunysb.edu/~skiena/combinatorica/grapheditor

You can use that graph editor on-line as an applet—you'll need a Java plug-in for your browser.  Or, you can download it as a Java .jar file and run it from a Java interpreter.

Using the on-line, applet version of the graph editor

From the graph editor web page, click the applet version link.

It's pretty obvious what to do next:  From the Vertex menu, select Add Vertex.  Then click wherever you want a vertex.  Next, from the Edge menu select Add Edge.  Click the vertex that will be one end of the edge, hold down the mouse button, and drag the line that appears to the vertex that will be the other end of the edge.  There are a lot more choices you can make, but those will get you started.

After you create the graph in the graph editor, save it as a file.  The file will contain the Mathematica Graph expression for the graph you drew.  Open the file in a text editor (e.g., Notepad, in Windows) and copy it to a Mathematica input cell.

Using the downloadable .jar file version of the graph editor

To use the downloadable .jar file version of the graph editor, you will need a copy of Java on your computer.  To start the graph editor, use a command of the form:
	c:\path_to_java.exe\java -jar GraphEditor.jar

It's pretty obvious what to do next:  From the Vertex menu, select Add Vertex.  Then click wherever you want a vertex.  Next, from the Edge menu select Add Edge.  Click the vertex that will be one end of the edge, hold down the mouse button, and drag the line that appears to the vertex that will be the other end of the edge.  There are a lot more choices you can make, but those will get you started.

After you create the graph in the graph editor, save it as a file.  The file will contain the Mathematica Graph expression for the graph you drew.  Open the file in a text editor and copy it to a Mathematica input cell.

You can also save a Mathematica Graph expression to a file from Mathematica, edit the graph in the graph editor, and then insert the edited graph back into a Mathematica cell.

Method 10:  Use a "rule-list"—see the section Displaying graphs with GraphPlot

Displaying graphs with ShowGraph

The basic function for displaying graphs is ShowGraph, as illustrated in many examples above.  For example:

newG = Cycle[3]
ShowGraph[newG]

To learn what options are available when you display a graph with ShowGraph, and what the default values are for these options, evaluate the following cell:

Options[ShowGraph]

Labeling edges and vertices

Earlier you saw how to number or otherwise label vertices, by using the VertexNumber option in ShowGraph.

The analog EdgeLabel->True, for edges, of the VertexNumber->True option for numbering vertices does not give particularly useful results, since it just numbers the edges without indicating which numbered edge joins which vertices.

ShowGraph[g,EdgeLabel->True]

Typically, then, you would use the EdgeLabel option with an explicit list of labels as value.  For example:

Edges[Wheel[4]]

g = Wheel[4];
ShowGraph[g,EdgeLabel->Characters["abcdef"]]

You may use the EdgeLabelPosition option to specify the edge labels' position relative to the edges.  For example:

ShowGraph[Wheel[4],EdgeLabel->Characters["abcdef"],EdgeLabelPosition->LowerRight]

You may use the BaseStyle option to format all the vertex labels or edge labels the same way. For example:

ShowGraph[Wheel[4],VertexLabel->{"x","y","z","w"},EdgeLabel->Characters["abcdef"],BaseStyle->{FontSize->16,FontSlant->"Italic",FontFamily->"Helvetica",FontWeight->"Bold"}]

Each of the font style options FontSize, FontSlant, FontFamily, and FontWeight may be used individually or in any combination with the others. Unfortunately, the FontColor style option has no effect within a ShowGraph BaseStyle option specification. To change font color, specify it instead within a Style expression for the vertex labels or edge labels, as in the following example.

ShowGraph[Wheel[4],VertexLabel->(Style[#,FontColor->Red]&)/@{"x","y","z","w"},
EdgeLabel->(Style[#,FontWeight->"Bold",FontColor->Green]&)/@Characters["abcdef"],
BaseStyle->{FontSize->16,FontSlant->"Italic"}]

The preceding example used both BaseStyle and mapping of Style onto the vertex and edge labels.  You could instead use Style alone, including all the formatting directives you need within it.

Using ShowGraph options as part of the structure of a graph

You may include as part of the structure of a graph object the options you would otherwise use with ShowGraph (and then you need not include the option again when you use ShowGraph).

An easy way to do this is by using the SetGraphOptions function.  For example:

g=SetGraphOptions[Wheel[4],VertexNumber->True]

ShowGraph[g]

Notice that you actually have to assign the SetGraphOptions expression as the new value of the graph.

Instead of using SetGraphOptions, you may include options directly as part of the definition of a Graph object—even though the red syntax-coloring seems to indicate something is wrong. For example:

myG=Graph[{{{1,2}}, {{2, 3}}}, {{{0,0}}, {{1,0}}, {{1,1}}}, VertexNumber->True,EdgeLabel->{"a","b"}]
ShowGraph[myG]

Changing the style of vertices or edges

g = Wheel[4];
ShowGraph[g,VertexStyle->Disk[Large],VertexColor->Yellow, VertexNumber->True,VertexNumberColor->Red,VertexNumberPosition->Center,BaseStyle->{FontWeight->"Bold"}]

g = Wheel[4];
ShowGraph[g,EdgeStyle->Thick,EdgeColor->Magenta,EdgeLabel->(Style[#,FontSize->14]&)/@{"a","b","c","d","e","f"},EdgeLabelColor->Blue]

To learn what colors are available, use the ColorSchemes palette (select it from the Palettes menu item).  Within the Named colors, those listed as System are ones you can just use by their names: Red, Blue, Green, Orange, etc.  For a color listed as Legacy, use the form ColorData["Legacy",name].  For example:

mycolor=ColorData["Legacy","CadmiumOrange"]
Graphics[{mycolor,Disk[]},ImageSize->25]

You may also use directly the built-in Mathematica function RGBColor to manufacture your own color combinations.

If used discretely, the various style options for vertices and edges can enhance a graph display.  Used carelessly, they can produce truly hideous displays!

Highlighting vertices or edges

Here is a depiction of a wheel graph:

g=Wheel[4];
ShowGraph[g,VertexNumber->True]

To highlight particular vertices or edges, use the Highlight function, which returns a new graph having the designated vertices or edges highlighted.  The second argument is the list of what is to be highlighted.  Notice that lists of edges to be highlighted must be doubly nested within the overall list second argument.

ShowGraph[Highlight[g,{1,2}],VertexNumber]
ShowGraph[Highlight[g,{{{1, 2}}}]]

ShowGraph[Highlight[g,{1,2}]]
ShowGraph[Highlight[g,{{1,2},{{3, 4},{4, 2}},{3},{{1,2}}}]]

By default, specific colors are used for the successively highlighted vertices and edges.  These colors can be changed if you wish, as can the default highlighting treatment of vertices as style Disk[Large] and edges as style Thick.  For details, evaluate the following cell:

?Highlight

Displaying several graphs in a single graphic

The Combinatorica unction ShowGraphArray displays a table of graphs.  The dimensions of the list argument to ShowGraphArray determines the shape of the table shown.

ShowGraphArray[{EmptyGraph[4],Cycle[4],CompleteGraph[4],CompleteGraph[2,2]}]

ShowGraphArray[{
{ EmptyGraph[4],Cycle[4]},
{CompleteGraph[4],CompleteGraph[2,2]}
}]

Moving graphs around

For the best display of a graph, it sometimes can help to move it in the plane.

w=Wheel[4];ShowGraph[w,VertexNumber->True]

ShowGraph[RotateVertices[w,-π/6],VertexNumber->True]

?ShakeGraph

ShowGraph[ShakeGraph[w,0.4],VertexNumber->True]

Displaying graphs with GraphPlot

The simplest way to display a graph created by means of Combinatorica functions is to use the Combinatorica function ShowGraph. Many examples of using ShowGraph appear in the preceding section. However, for finer control over the appearance of vertices and edges and their labels, you may want to use instead the Mathematica 6 kernel function GraphPlot.

For a first example, we'll use the 3-cycle:

(Subscript[C, 3]) = Cycle[3];

Compare the results of using ShowGraph and GraphPlot:

{ShowGraph[(Subscript[C, 3])],GraphPlot[(Subscript[C, 3])]}

GraphPlot has made two changes in the appearance of the graph: the edge color is no longer black, and the vertices have moved to new locations. To keep the vertices in the same locations, include the GraphPlot option Method->None. (Values other than None for the Method option specify different ways to position the vertices.)

GraphPlot[(Subscript[C, 3]),Method->None]

Displaying a rule-list type of graph with GraphPlot

One advantage of GraphPlot is that you may use it to display a graph without having first to create an actual Graph[...] type of object by means of Combinatorica functions. The type of graph that is "native" to GraphPlot is just a list of rules, each rule having the form u->v to represent an edge incident with vertices u and v (and, in the case of a directed graph, with initial vertex u and terminal vertex v).

GraphPlot[{1->2,2->4,1->3,2->3,1->4}]

GraphPlot[{1->2,2->4,1->3,2->3,1->4},VertexLabeling->True]

See the following section for more about displaying and styling vertex labels.

The method for specifying vertices and the edges incident with those vertices in GraphPlot is similar to the method used by the Combinatorica function FromOrderedPairs:

ShowGraph[FromOrderedPairs[{{1,2},{2,4},{1,3},{2,3},{1,4}},Type->Undirected],VertexNumber->True]

It is easy to specify multiple edges joining two vertices or loops:

GraphPlot[{1->2,2->3,2->3,3->4,4->1,1->3,4->4,1->1,1->1},VertexLabeling->True]

Notice that you do not want to use the Method->None option when you create a graph as a rule-list within GraphPlot. However, you may want to use other settings for Method, which indicate how to locate the vertices in the plane.

GraphicsRow[{GraphPlot[{1->2,2->3,3->4,4->1,1->3},Method->"CircularEmbedding",VertexLabeling->True],
GraphPlot[{1->2,2->3,3->4,4->1,1->3},Method->"RandomEmbedding",VertexLabeling->True]}]

The vertices of a rules-list type of graph do not need to be numbers at all. For example:

GraphPlot[{"winter"->"spring","spring"->"summer","summer"->"fall","fall"->"winter"},VertexLabeling->True,DirectedEdges->True]

See the section "Working with digraphs" for information about directed graphs, such as the preceding one.

Another advantage of GraphPlot is the ease with which you can visualize relations among mathematical objects or data objects.

Example: coprimality graph

Below will shall create and display in xxx ways a graph whose vertices represent integers from 1 through 10, and in which two vertices are adjacent exactly when the two integers are "coprime", that is, relatively prime to one another.

We'll build this in several stages. We begin by defining a function to test for coprimality and a function that creates an edge representation m->n when positive integers m and n are in fact coprime.

For all xxx the methods, we begin by defining a function that tests for coprimality but that returns 1 or 0, respectively, instead of True or False; the function Boole does the needed conversion from True and False.

(*coprime[m_Integer,n_Integer]:=Boole[GCD[m,n]==1]*)

coprime[m_Integer,n_Integer]:=GCD[m,n]==1

coprimeRule[m_Integer,n_Integer]:=If[coprime[m,n]&&m≤n,m->n]

coprimeRuleList=Cases[Union@Flatten@Table[coprimeRule[a,b],{a,1,8},{b,1,8}],Except[Null]]

GraphPlot[coprimeRuleList,VertexLabeling->True,Method->CircularEmbedding]

The function GraphPlot can also take as argument an adjacency matrix instead of a rule-list.

Table[If[coprime[a,b],1,0],{a,1,10},{b,1,10}]//MatrixForm

GraphPlot[Table[If[coprime[a,b],1,0],{a,1,8},{b,1,8}],VertexLabeling->True,Method->CircularEmbedding,SelfLoopStyle->0.4]

For example:

{coprimeRule[4,9],coprimeRule[6,9],coprimeRule[9,4]}

The reason for the condition m ≤ n in the definition of coprimeRule is to obtain only one edge, not two, incident with a given pair of coprime integers.

Let's examine just the integers from 1 to 10. The edges to be created for our graph will be the entries in the table below that are not Null:

Outer[coprimeRule,Range[10],Range[10]]

Now flatten this list of lists to a single list and remove all its Null entries:

coprimeEdges=Cases[Flatten@Outer[coprimeRule,Range[10],Range[10]],Except[Null]]

GraphPlot[coprimeEdges,VertexLabeling->True]

data graph

Our final example here of forming a rules-list graph and displaying it with GraphPlot is rather fanciful. The vertices will be some baby animals—three-dimensional graphics images of these animals, actually. To form those 3D images, we use one of the integrated data sources of Mathematica 6, namely, the ExampleData database. (Mathematica 6 can directly access numerous databases in formats suitable for direct processing in Mathematica: geographical data, chemical data, astronomical data, financial data, etc.)

Here is the first animal we'll use—a cow. Access it from the Geometry3D database as follows:

ExampleData[{"Geometry3D","Cow"}]

We'll use three more animals.  Here are all four, defined at once. (⌚You may have to wait a few seconds while Mathematica obtains the objects from the database; please be patient!)

{cow,rabbit,horse,triceratops}=ExampleData[{"Geometry3D",#}]&/@{"Cow","StanfordBunny","Horse","Triceratops"};

These 3D graphics images will be too big to insert at vertices in our graph, so we shrink their sizes by directly manipulating their underlying representation (don't worry here about the details!):

shrinkAnimal[creature_]:=creature/.(Boxed->False)->Sequence[Boxed->False,ImageSize->60]

{calf,bunny,colt,dino}=shrinkAnimal/@{cow,rabbit,horse,triceratops}

Finally, we create some connecting edges—don't ask what the edges mean in this fanciful example!—and display the resulting graph:

GraphPlot[{colt->calf,calf->bunny,bunny->colt,colt->dino,calf->dino},VertexLabeling->True]

⚠ If you now save this notebook, you will have a multi-megabyte file, because of the preceding 3D graphics objects. You should probably delete the output cells with these images before saving the notebook. (Indeed, you may want to delete all output cells by using the menu command Cell ▸ Delete All Output.)

Converting between rule-list graphs and Combinatorica Graph objects

The following function converts the usual Combinatorica Graph type of object to the list of rules such as is expected by GraphPlot.

RuleListFromGraph[Graph[edges_,vertices_,___]]:=Module[{vrules},vrules=DeleteCases[Thread[Range[Length[vertices]]->(VertexLabel/.vertices[[All,2;;]])],_->VertexLabel];
Replace[Transpose[{Rule@@@(edges[[All,1]]/.vrules),EdgeLabel/.edges[[All,2;;]]}],{a_,EdgeLabel}->a,{1}]]

⚠ Caution: RuleListFromGraph is not a built-in Mathematica function! You will need to evaluate its definition before using it. Its definition was included in the Initialization section of this notebook.

For example:

RuleListFromGraph[Wheel[4]]

Thus the first example of the preceding section could have been created from Wheel[4] as follows:

GraphPlot[RuleListFromGraph[Wheel[4]]]

An advantage of letting RuleListFromGraph act upon a Graph object, rather than just create the list of rules directly, is that RuleListFromGraph preserves the information about vertex and edge labels.

g=Wheel[4];
g=SetVertexLabels[g,Range[4]];
g=SetEdgeLabels[g,Characters["defabc"]];
g=RuleListFromGraph[g];

GraphPlot[g,VertexLabeling->True,EdgeLabeling->True,BaseStyle->{FontSize->16}]

Unfortunately, the original coordinates of the vertices are lost once RuleListFromGraph is applied. In order to preserve the vertex coordinates, too, for use with GraphPlot, we use the following additional function GetVertexCoordinates:

GetVertexCoordinates[Graph[edges_,vertices_,___]]:=vertices[[All,1]]

⚠ Caution: GetVertexCoordinates is not a built-in Mathematica function! You will need to evaluate its definition before using it. Its definition was included in the Initialization section of this notebook.

With the aid of this function, we can almost reproduce with GraphPlot the display from ShowGraph, keeping the vertex coordinates and showing both vertex labels and coordinate labels. For example:

g=SetEdgeLabels[
SetVertexLabels[Wheel[4],Range[4]],
Characters["defabc"]];
GraphPlot[RuleListFromGraph[g],VertexLabeling->True,VertexCoordinateRules->GetVertexCoordinates[g]]

There is still one issue here: The default vertex label style and default edge style may not be what you want. See the following two subsections for how to resolve this issue with GraphPlot.

Converting from rule-list graph to Combinatorica Graph object

Consider a "rule-list" such as may be used as the first argument to GraphPlot. Here's an example:

g={1->4,2->4,3->4,1->2,2->3,1->3,1->1,1->3};

It is easy to convert such a "rule-list"into a genuine Combinatorica-type Graph object. Two steps are involved:
	• convert each u->v item into a list {u,v}; and then
	• feed the resulting list of two-member lists into FromOrderedPairs.

Do the first step by means of a pattern-substitution rule:

g/.{(v_->w_)->{v,w}}

Define a function to do that:

OrderedPairsFromRuleList[lis_]:=lis/.{(v_->w_)->{v,w}}

Do the second step in the conversion by using FromOrderedPairs:

newg=FromOrderedPairs[OrderedPairsFromRuleList[g]]

That is indeed a Combinatorica Graph object. And now you may display it in the usual Combinatorica way:

ShowGraph[FromOrderedPairs[OrderedPairsFromRuleList[g]]]

Labeling and styling vertices with GraphPlot

Vertex appearance in a GraphPlot display, including labeling of vertices, is controlled by the option VertexRenderingFunction. The value specified for this option should  be a pure function whose dummy argument refers to the vertex location. For example, make the vertices larger disks:

GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->(Disk[#,0.04]&)]

The parameter value 0.04 above specified the radius of the vertex disks relative to the size of the entire figure; the large this number, the large the radius.

When you use, as in the preceding example, an expression of the form …#… & for the pure function that is the value of VertexRenderingFunction, then you must enclose that expression in parentheses. Otherwise, you will get a syntax error. You could also use, instead, a Function[x,…x…] form, and then you would not need the parentheses.

GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->Function[vertex,Disk[vertex,0.04]]]

Here are some variations where the color of each vertex disk is changed, or the disk is rendered with a contrasting bounding circle. Notice that the body of the pure function is now a list which, like any list must be enclosed in braces.

GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->({Blue,Disk[#,0.04]}&)]
GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->({EdgeForm[{Red,Thick}],Yellow,Disk[#,0.05]}&)]

To turn on vertex labeling in a GraphPlot display, include the option VertexLabeling-->True. By default, vertex labels in a GraphPlot display are shown centered at the vertices, not nearby as was the case with ShowGraph.

GraphPlot[Wheel[4],Method->None,VertexLabeling->True]

Notice how nicely GraphPlot formats the vertex labels. Of course you can still control the color, shape, and boundary of the vertex as before—but then you will need to specify explicitly a Text expression within the value of the VertexRenderingFunction.

GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->({EdgeForm[{Red,Thick}],Yellow,Disk[#,0.05],Black,Text[#2,#1]}&)]

In the Text expression above, the argument #1, which means the same thing as just # within this pure function, refers again to the vertex location, whereas the argument #2 refers to the text that is going to be displayed there, namely, the vertex label.

You may change the appearance of the text in the usual ways: with a BaseStyle option to GraphPlot; with a Style expression that includes the Text expression; or with some combination of both ways. For example:

GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->({EdgeForm[{Red,Thin}],White,Disk[#,0.05],Black,Text[#2,#1]}&),BaseStyle->{FontSize->14,FontSlant->"Italic",FontWeight->"Bold",FontFamily->"Helvetica"}]

If you want vertex labels that are not just the default numbers, you will have to specify a more complicated Text expression within the VertexRenderingFunction. In this Text expression, use the slot argument #2 to pick out which of a list of labels you want. For example:

GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->({EdgeForm[{Black}],White,Disk[#1,0.05],Black,Text[{"a","b","c","d"}[[#2]],#1]}&),BaseStyle->{FontSize->16}]

It is a bit neater to define the vertex label list separately, outside the GraphPlot expression. But then it is a good idea to localize the name used for that list within a With (or Module):

With[{labels={"a","b","c","d"}},
GraphPlot[Wheel[4],Method->None,VertexRenderingFunction->({EdgeForm[{Black}],White,Disk[#1,0.05],Black,Text[labels[[#2]],#1]}&),BaseStyle->{FontSize->16}]
]

The vertex labels produced by the following GraphPlot expression are hidden, but mousing over a vertex reveal its label in a tooltip.

GraphPlot[Wheel[4],Method->None,VertexLabeling->Tooltip]

GraphPlot[Wheel[4],Method->None,VertexLabeling->Tooltip, VertexRenderingFunction->({Disk[#,0.04],Tooltip[Text[#2,#1]]}&)]

And you may combine tooltip labeling with non-default labels.

With[{labels=Characters["abcd"]},GraphPlot[Wheel[4],Method->None,VertexLabeling->Tooltip, VertexRenderingFunction->({Blue,Disk[#,0.04],Black,Tooltip[Text[labels[[#2]],#1]]}&)]
]

Labeling and styling edges with GraphPlot

Edge appearance in a GraphPlot display, including labeling of edges, is controlled by the option EdgeRenderingFunction. As with VertexRenderingFunction, the value specified for this option should be a pure function whose dummy argument refers to the vertex location. For example, make the edges thicker and black instead of the default brown:

GraphPlot[Wheel[4],Method->None,EdgeRenderingFunction->({Black,Thick,Line[#]}&)]

Unfortunately, at present it is not easy to display edge labels when you apply GraphPlot to a Graph object created with Combinatorica functions. We illustrate two cumbersome methods here, both suggested in MathGroup by Carl Woll of Wolfram Research.

For vertices, the examples in this section use the GraphPlot default—a rather small disk. To change that, or to label the vertices, too, use the methods shown in the preceding section.

Method 1: insert edge labels in the Graph object; strip out vertex coordinates; and use the EdgeLabeling->True option to GraphPlot

Start with the graph build using Combinatorica functions. For example:

g=Wheel[4];

The next step is going to be to use the Combinatorica function SetEdgeLabels to build the desired edge labels into the Graph object. Before proceeding, however, you may want to examine the order in which the edges appear in this Graph object, since that is the order in which the edge labels you specify will be used.

InputForm@First[g]

The eges are {1, 4}, {2, 4}, {3, 4}, {1, 2}, {2, 3}, {1, 3}, in that order. Suppose you want to give the edge {1,2} from vertex 1 to vertex 2 the label "a", the edge {2,3} the label "b", etc. Then you would use SetEdgeLabels like this:

g=SetEdgeLabels[g,{"d","e","f","a","b","c"}];

Note that the internal structure of g has now changed: the edge labels have been incorporated into the very definitions of the edges.

InputForm@First[g]

(If you don't care which edge is labeled with what particular label, then just specify the labels in any order, e.g., alphabetical: g=SetEdgeLabels[g,Characters["abcdef"]].)

At this point, the following should work—but it does not: there are no edge labels after all!

Head[g]

GraphPlot[g,EdgeLabeling->True]

The following function  StripVertexCoordinates provides a work-around to use after you have already built the edge labels into the Graph object (by using SetEdgeLabels, as above, or otherwise). Feel free to use this function even if you do not understand how it does what it does.

⚠ Caution: StripVertexCoordinates is not a built-in Mathematica function! You will need to evaluate its definition before using it. Its definition was included in the Initialization section of this notebook.

StripVertexCoordinates[g_Graph]:=Replace[First@g,{{a_,b_},opts___}:>(If[MatchQ[#,EdgeLabel],a->b,{a->b,#}]&[EdgeLabel/.{opts}]),{1}];

g=StripVertexCoordinates[g];

The result, as you can see from the next output, is to strip out the vertex coordinates completely from the graph structure and convert the entire Combinatorica Graph object to a  rule-list type of graph representation, while preserving the edge labels.

InputForm[g]

Finally, display the graph:

GraphPlot[g,BaseStyle->{FontSize->16,FontSlant->Italic}]

Here again is the entire procedure:

g=Wheel[4];
g=SetEdgeLabels[g,Characters["defabc"]];
g=StripVertexCoordinates[g];
GraphPlot[g,BaseStyle->{FontSize->16,FontSlant->Italic}]

This method has two defects:
• First, the edge labels are displayed upon, rather than near, the edges. An unpleasant result may be, as in our example, that one edge label obscures another in the same location, at the middle of the two edges. (Edge label c has disappeared beneath edge label e.)
• Second, the vertex coordinates of the original Graph object have been lost. (And so the usual option Method->None is not even permitted; using it would produce an error.) The result is that GraphPlot uses the default setting Method->Automatic and chooses where to locate the vertices now. In our example, the effect is unpleasant: the edges are skewed from horizontal and vertical.

To retain the vertex of the original Graph object, use the function GetVertexCoordinates together with the VertexCoordinateRules option to GraphPlot.

g=Wheel[4];
g=SetEdgeLabels[g,Characters["defabc"]];
g=StripVertexCoordinates[g];
GraphPlot[g,BaseStyle->{FontSize->16,FontSlant->Italic}]

g=SetEdgeLabels[
SetVertexLabels[Wheel[4],Range[4]],
Characters["defabc"]];
GraphPlot[RuleListFromGraph[g],VertexLabeling->True,VertexCoordinateRules->GetVertexCoordinates[g]]

You may, of course, try another value for Method to see if the results will look better. Some experimentation may be required in order to find a Method setting that keeps one label from obscuring another. In our example, the "RadialDrawing" method accomplishes that goal:

GraphPlot[g,Method->"RadialDrawing",BaseStyle->{FontSize->16,FontSlant->Italic}]

Under construction!

Method 2: use the EdgeRenderingFunction option to GraphPlot

The EdgeRenderingFunction here employs the ruse of constructing two arrows between each pair of adjacent vertices—one arrow in each direction—but with the head of each arrow being the edge label. (Thus each edge label is written twice!)

ShowGraph[g]

g=Wheel[4];
labels=Characters["defabc"];
edgeLabelFunction[{u_,v_}]:=labels[[First@Flatten@Position[Edges[g],{u,v}|{v,u}]]]

GraphPlot[g,Method->None,EdgeRenderingFunction->({Arrowheads[{{0.5,0.5,Graphics[{Black,Inset[Style[edgeLabelFunction[#2]],{0,0},ImageScaled[{0.5,0.5}],Automatic,None,Background->White]}]}}],Arrow[#1]}&),
BaseStyle->{FontSize->16,FontSlant->"Italic"}]

Observe that with this method, unlike with the first method, the vertex coordinates are preserved.

Highlighting vertices or edges

Under construction!

Here is a depiction of a wheel graph:

g=Wheel[4];
ShowGraph[g,VertexNumber->True]

To highlight particular vertices or edges, use the Highlight function, which returns a new graph having the designated vertices or edges highlighted.  The second argument is the list of what is to be highlighted.  Notice that lists of edges to be highlighted must be doubly nested within the overall list second argument.

ShowGraph[Highlight[g,{1,2}],VertexNumber]
ShowGraph[Highlight[g,{{{1, 2}}}]]

ShowGraph[Highlight[g,{1,2}]]
ShowGraph[Highlight[g,{{1,2},{{3, 4},{4, 2}},{3},{{1,2}}}]]

By default, specific colors are used for the successively highlighted vertices and edges.  These colors can be changed if you wish, as can the default highlighting treatment of vertices as style Disk[Large] and edges as style Thick.  For details, evaluate the following cell:

?Highlight

Displaying several graphs in a single graphic

Recall that to display several graphs at once, you could use ShowGraphArray. However, if you have graphs whose display requires GraphPlot, then you should not use ShowGraphArray, but one of the kernel functions GraphicsRow, GraphicsColumn, or GraphicsGrid.

GraphicsRow[GraphPlot/@{EmptyGraph[4],Cycle[4],CompleteGraph[4],CompleteGraph[2,2]}]

GraphicsRow[GraphPlot/@{EmptyGraph[4],Cycle[4],CompleteGraph[4],CompleteGraph[2,2]}]

GraphicsRow[GraphPlot[#,Method->None]&/@{EmptyGraph[4],Cycle[4],CompleteGraph[4],CompleteGraph[2,2]}]

GraphicsGrid[{
{ GraphPlot[EmptyGraph[4]],GraphPlot[Cycle[4]]},
{GraphPlot[CompleteGraph[4]],GraphPlot[CompleteGraph[2,2]]}
}]

Of course, you may embellish the graphs included in such a GraphicsGrid-like expression in any of the usual ways—by using a VertexRenderingFunction, EdgeRenderingFunction, etc. And you may control spacing between the constituent graphs by options to GraphicsGrid, etc.

GraphicsGrid[Partition[GraphPlot[#,Method->None,VertexRenderingFunction->({EdgeForm[{Red,Thick}],Yellow,Disk[#,0.15],Black,Text[#2,#1]}&),BaseStyle->{FontSize->12}]&/@Table[CompleteGraph[n],{n,2,5}],2]]

Creating graphs within GraphPlot under revision

One advantage of GraphPlot over ShowGraph is that you can completely specify a graph within GraphPlot without having to create an actual Combinatorica-type Graph object. You just specify which vertex is to be adjacent to which vertices in a single list. Each entry in that list has the form u->v, meaning that v is adjacent to u (and, when the graph is directed, that the direction is from u to v). For example:

GraphPlot[{1->2,2->3,3->4,4->1,1->3},VertexLabeling->True]

It is now easy to specify multiple edges joining two vertices or loops:

GraphPlot[{1->2,2->3,2->3,3->4,4->1,1->3,4->4,1->1,1->1},VertexLabeling->True]

Notice that you do not want to use the Method->None option when you create a graph like this directly within GraphPlot. However, you may want to use other settings for Method, which indicate how to locate the vertices in the plane.

GraphicsRow[{GraphPlot[{1->2,2->3,3->4,4->1,1->3},Method->CircularEmbedding,VertexLabeling->True],
GraphPlot[{1->2,2->3,3->4,4->1,1->3},Method->RandomEmbedding,VertexLabeling->True]}]

With such direct use of GraphPlot to create graphs, of course you may still use VertexRenderingFunction and EdgeRenderingFunction to treat vertices and edges as you wish.

The vertices you specify within GraphPlot need not be positive integers. In fact, they can be just about anything you might want. For example:

GraphPlot[{"start"->(Subscript[v, 1]),(Subscript[v, 1])->(Subscript[v, 3]),(Subscript[v, 1])->somewhere,somewhere->"end"},VertexLabeling->True]

Moreover, Another advantage of GraphPlot is that you may specify graphs based upon mathematical relations or relations among data objects. For example, the next graph has integers 1, 2,  …, 8 as vertices and has two vertices adjacent exactly when these integers are relatively prime to one another.

GraphPlot[Table[If[GCD[a,b]== 1,1,0],{a,1,8},{b,1,8}],VertexLabeling->True,Method->CircularEmbedding]

Mathematica can access on demand all sorts of data from standard databases, for example, from geographical databases. And then that data may be used to visualize relationships between data entities by means of a graph. For example, the following graph has countries of Central America as vertices and has two such countries adjacent in the graph if they share a geographical border.

GraphPlot[Flatten[Thread[#->CountryData[#,"BorderingCountries"]]&/@CountryData["CentralAmerica"]],VertexLabeling->True,MultiedgeStyle->False,Method->CircularEmbedding]

The downside of creating a graph directly within a GraphPlot expression is that you do not have a Combinatorica-type Graph object and hence cannot apply Combinatorica graph-theoretical functions to this object.

g={1->2,2->3,3->4,4->1,2->4,2->5,4->5};

GraphPlot[g,VertexLabeling->True]

DegreeSequence[g] (* this won't work! *)

EulerianQ[g] (* this won't work either! *)

However, it is easy to convert a list like g into a genuine Combinatorica-type Graph object—see above the subsection Converting from rule-list graph to Combinatorica Graph object. In that section, a function OrderedPairsFromRuleList is defined to do part of the conversion, and then FromOrderedPairs does the rest.
Two steps are involved: First, convert each u->v item into a list {u,v}; second, feed the resulting list of two-member lists into FromOrderedPairs. The way to do the first step is by means of an actual pattern-substitution rule:

myG=FromOrderedPairs[OrderedPairsFromRuleList[g],Type->Undirected]

Now Combinatorica functions may be applied:

DegreeSequence[myG]

EulerianQ[myG]

Vertices and edges

The Combinatorica function Edges gives the list of edges of a graph.  And the function Vertices gives the actual coordinates of the points in the plane that represent the vertices of the graph.

g=CompleteGraph[5];

Edges[g]

Vertices[g]

To find the number of vertices and the number of edges, calculate the lengths of those lists:

Length/@{Vertices[g],Edges[g]}

Or, use directly the Combinatorica function V for the number of vertices, and the function M for the number of edges, of a graph.

{V[g],M[g]}

Degrees

The Degrees function returns the list of degrees of all the vertices of a graph, in the same order as the vertices themselves appear in the underlying Graph structure.  For example:

g=FromOrderedPairs[{{1,2},{1,4},{2,4},{3,4},{4,5}},Type->Undirected];
ShowGraph[g,VertexNumber->True]

Degrees[g]

By contrast, DegreeSequence returns the list of all degrees in descending order, with each degree appearing as many times as there are vertices having that degree.

DegreeSequence[g]

Graph isomorphisms

(Subscript[g, 1])

(Subscript[g, 2])

For two graphs (Subscript[g, 1]) and (Subscript[g, 2]), the expression IsomorphicQ[(Subscript[g, 1]),(Subscript[g, 2])] tells whether its two arguments are isomorphic as graphs.

(Subscript[g, 1]) = CompleteGraph[3, 3];
(Subscript[g, 2]) = AddEdges[Cycle[6], {{1,4}, {2,5}, {3,6}}];
ShowGraphArray[{(Subscript[g, 1]), (Subscript[g, 2])},VertexNumber ->True]

IsomorphicQ[(Subscript[g, 1]),(Subscript[g, 2])]

IsomorphicQ[(Subscript[g, 1]), CompleteGraph[6]]

The expression Isomorphism[(Subscript[g, 1]),(Subscript[g, 2])] produces an isomorphism from (Subscript[g, 1]) to (Subscript[g, 2]) if there is one.  For the particular isomorphism produced, the result is the list of vertex numbers of (Subscript[g, 2]) that correspond, in order, to vertex numbers 1, 2, etc., of (Subscript[g, 1]).

Isomorphism[(Subscript[g, 1]),(Subscript[g, 2])]

The additional argument All to Isomorphism produces a list of all isomorphisms between the two graphs.

Isomorphism[(Subscript[g, 1]),(Subscript[g, 2]),All]

Simple graphs

To test whether a graph is simple, use SimpleQ:

SimpleQ[Wheel[4]]

To produce a non-simple graph, you may use AddEdge or AddEdges to introduce multiple edges and self-loops:

g=Cycle[3];g=AddEdges[g,{{1,2},{3, 3}}]; ShowGraph[g]

SimpleQ[g]

To make a non-simple graph simple, you could manually use RemoveEdge or RemoveEdges.with the specific edge(s) as second argument.  A simpler way is to use RemoveSelfLoops and RemoveMultipleEdges:

s1=RemoveMultipleEdges[g];ShowGraph[s1]
SimpleQ[s1]

s2=RemoveSelfLoops[s1];ShowGraph[s2]
SimpleQ[s2]

An even simpler way to make a non-simple graph simple is to use MakeSimple:

SimpleQ[g]

s=MakeSimple[g];ShowGraph[s]
SimpleQ[s]

Adjacency matrix of a graph

The adjacency matrix M of a graph G having n vertices (Subscript[v, 1]),(Subscript[v, 2]),…,(Subscript[v, n]) is a matrix of 0's and 1's that has a 1 in its (i,j)th entry if and only if vertex (Subscript[v, i]) is adjacent to vertex vj, in other words if and only if (Subscript[v, i])and (Subscript[v, j]) are the ends of the same edge.

The Combinatorica functions ToAdjacencyMatrix and FromAdjacencyMatrix  convert a Graph object to its adjacency matrix representation and vice versa.

Forming the adjacency matrix of a given graph: ToAdjacencyMatrix

g=RandomGraph[5,0.6];
ShowGraph[g,VertexNumber ->True]

V[g]

a = ToAdjacencyMatrix[g]

The result of ToAdjacencyMatrix is a list of lists in which the inner lists represent the rows of the matrix.  To display the list result of ToAdjacencyMatrix as a matrix, use the MatrixForm function:

MatrixForm[a]

The order of vertices used in forming the adjacency matrix is the order of the vertices in the second argument of the underlying Graph expression—hence the same order as shown if you use the VertexNumber->True option in ShowGraph.

It's often convenient to use suffix notation // with MatrixForm.  For example:

ToAdjacencyMatrix[g]//MatrixForm

⚠  Caution.  The result returned by MatrixForm is merely a form of display and not a true matrix (that is, not a list of lists) suitable for further computation.

(* wrong! *)     a=ToAdjacencyMatrix[g]//MatrixForm

What's wrong with that?  Try, say, to form the matrix product of the adjacency matrix with itself using the . notation:

a . a

(* right *)     a=ToAdjacencyMatrix[g];a//MatrixForm

a . a

% // MatrixForm

The (i, j)th entry in the square a . a of the adjacency matrix is the number of walks of length 2 in the graph from the ith vertex to the jth vertex.  Similarly, the entries of a . a . a give the number of walks of length 3:

a . a . a//MatrixForm

For higher powers, especially, it's convenient to use the Mathematica function MatrixPower:

MatrixPower[a,3]//MatrixForm

MatrixPower[a,6]//MatrixForm

To add any two matrices of the same shape, use +.  To add successive powers of an adjacency matrix (or other square matrix), you may use either Sum or Apply[Plus, ...] .  For example:

n=Length[Vertices[g]];
Sum[MatrixPower[a,j],{j,1,n}]//MatrixForm

Apply[Plus,Table[MatrixPower[a,j],{j,1, n}]]//MatrixForm

Here's the same thing as the preceding expression except using the @@ abbreviation for Apply and the /@ abbreviation for Map:

Plus@@(MatrixPower[a,#]&/@Range[n])//MatrixForm

Creating a graph from its adjacency matrix: FromAdjacencyMatrix

The Combinatorica function FromAdjacencyMatrix provides a convenient way to create, among others, graphs having loops or multiple edges.  For example:

a={ {0,1,1,3},{1,1,1,0},{1,0,0,0},{3,0,0,0} }; a//MatrixForm

ShowGraph[FromAdjacencyMatrix[a],VertexNumber->True]

Note that the convention used for loops here differs from that used by some authors in graph theory.  Some authors say that each loop at the ith vertex contributes 2 to the entry in the (i, i)th diagonal entry of the adjacency matrix.  In the Combinatorica package, however, each loop at the ith vertex contributes 1 to the entry in the (i, i)th diagonal entry of the adjacency matrix, so that an entry of 2 would designate two different loops at the vertex.

For creating the adjacency matrix of a graph, you may wish to use the Mathematica menu item ▸Insert ▸ Create Matrix/Table/Palette ▸ New.  Put your cursor where you want to create the matrix.  In the pop-up dialog box,
• select the Matrix radio button;
• type the number of rows and columns;
• do not check any of the three Draw... boxes; and 
•  for a simple graph check the Fill diagonal checkbox and type 0 in the corresponding input field.
After you click the OK button in the dialog box, a matrix template such as the following one will appear at the current cursor position in the currently selected notebook.
	(({{0, □, □, □, □}, {□, 0, □, □, □}, {□, □, 0, □, □}, {□, □, □, 0, □}, {□, □, □, □, 0}})) 
Click the first placeholder box  in the fist row and type the desired entry of the matrix; press the ⇥ key to move from one placeholder box to the next and type each entry in turn.

Here's a smaller example created that way:

ShowGraph[FromAdjacencyMatrix[(({{0, 1, 1}, {1, 0, 0}, {1, 0, 0}}))],VertexNumber->True]

Example: coprimality graph

An adjacency matrix is a wBelow will shall create and display in xxx ways a graph whose vertices represent integers from 1 through 10, and in which two vertices are adjacent exactly when the two integers are "coprime", that is, relatively prime to one another.

xxx The first step will be to create methods

xx

The

We'll build this in several stages. We begin by defining a function to test for coprimality and a function that creates an edge representation m->n when positive integers m and n are in fact coprime.

For all xxx the methods, we begin by defining a function that tests for coprimality but that returns 1 or 0, respectively, instead of True or False; the function Boole does the needed conversion from True and False.

coprime[m_Integer,n_Integer]:=Boole[GCD[m,n]==1]

coprimeRule[m_Integer,n_Integer]:=If[coPrime[m,n]&&m≤n,m->n]

The adjacency matrix for the relation of coprimality GraphPlot can also take as argument an adjacency matrix instead of

GraphPlot[Table[If[coprime[a,b],1,0],{a,1,10},{b,1,10}],VertexLabeling->True,Method->CircularEmbedding]

For example:

{coprimeRule[4,9],coprimeRule[6,9],coprimeRule[9,4]}

The reason for the condition m ≤ n in the definition of coprimeRule is to obtain only one edge, not two, incident with a given pair of coprime integers.

Let's examine just the integers from 1 to 10. The edges to be created for our graph will be the entries in the table below that are not Null:

Outer[coprimeRule,Range[10],Range[10]]

Now flatten this list of lists to a single list and remove all its Null entries:

coprimeEdges=Cases[Flatten@Outer[coprimeRule,Range[10],Range[10]],Except[Null]]

GraphPlot[coprimeEdges,VertexLabeling->True]

Subgraphs

The only Combinatorica function that directly creates a subgraph of a given graph is InduceSubgraph.  Given a graph g and a list s consisting of some (or all) of the vertices of g, InduceSubgraph[g,s] produces a new graph having s as its list of vertices and having all the edges from the original graph g that join these vertices remaining in s.

For example, start with a complete graph on 4 vertices.

g=CompleteGraph[4];
g=SetGraphOptions[g,VertexNumber->True];ShowGraph[g]

h=InduceSubgraph[g,{1,3,4}];ShowGraph[h]

g=Cycle[3];ShowGraph[g,VertexNumber->True]

Notice that Combinatorica has renumbered the three vertices of this subgraph h as the default 1, 2, and 3; in the original graph g, these vertices were numbered 1, 3, and 4.  But we can see that the correct subgraph was formed, since the vertices of the subgraph remain the same objects—the same pairs of plane coordinates—as they were in the original graph.

To form an arbitrary subgraph of a graph, you may start with an induced subgraph and then use DeleteEdges to remove additional edges joining vertices that remain in the subgraph.

DeleteEdges[h,{1,2}]//ShowGraph

Connected graphs and graph components

The function ConnectedQ tests whether a graph is connected:

ConnectedQ[Star[3]]

g=GraphUnion[Cycle[3],Path[2]];ShowGraph[g,VertexNumber->True]
ConnectedQ[g]

The function ConnectedComponents produces a list of lists of vertices in the various components of a graph.

ConnectedComponents[g]

?*Subgraph*

To produce as an actual graph—a subgraph of the original graph—a component of a graph, just use InduceSubgraph.  For example:

{InduceSubgraph[g,ConnectedComponents[g][[1]]], InduceSubgraph[g,ConnectedComponents[g][[2]]]}
ShowGraph[#,VertexNumber->True]&/@%

Notice that in the second of the component subgraphs, Combinatorica has renumbered its vertices to the default numbers 1 and 2; originally, in the original graph g, these vertices were numbered 4 and 5.

Cycles; Eulerian and Hamiltonian graphs

The function FindCycle finds a cycle in a graph if there is one.  For example:

ShowGraph[g=DeleteEdges[Wheel[6],{{1,5},{5,6}}],VertexNumber->True]

FindCycle[g]

Notice that the preceding cycle does not include all the vertices of the graph g and does not traverse all the edges of g.

The function ExtractCycles finds a maximal list of edge-disjoint cycles in a graph.  For the preceding graph, in which vertex 5 cannot belong to any cycle, there is just a single such longest cycle, namely, the one already found:

ExtractCycles[g]

In the following (disconnected) graph, there are two such cycles:

g2=GraphUnion[Wheel[4],Cycle[4]];
ShowGraph[g2,VertexNumber->True]
ExtractCycles[g2]

Use EulerianQ to test whether a graph is Eulerian.

EulerianQ[Wheel[6]]
EulerianQ[CompleteGraph[2,2]]

Then to obtain an Eulerian cycle (what some folks call an Eulerian trail), use EulerianCycle:

ShowGraph[g=CompleteGraph[2,2],VertexNumber->True]
c=EulerianCycle[g]

To display an Eulerian cycle visually, you may wish to use AnimateGraph with second argument the list of successive edges of the Eulerian cycle; you can create an especially nice effect by suitably coloring the successive highlighted edges.

e=Partition[c,2,1]

AnimateGraph[g,e]

AnimateGraph[g,e,HighlightedEdgeColors->Red]

Use HamiltonianQ to test whether a graph is Hamiltonian.  Then to obtain a Hamiltonian cycle, use HamiltonianCycle:

HamiltonianQ[Wheel[6]]

ShowGraph[(Subscript[W, 6])=Wheel[6],VertexNumber->True]
c=HamiltonianCycle[(Subscript[W, 6])]

⚠ Caution.  The function HamiltonianQ can take a long time to return a result when the graph is sufficiently large.

AnimateGraph may be used to show dynamically how the a Hamiltonian cycle visits all the vertices in order.

AnimateGraph[(Subscript[W, 6]),c,
VertexColor->Blue,HighlightedVertexColors->Red,
VertexLabelColor->Purple,VertexLabelPosition->UpperLeft,VertexLabel->(Style[#,FontSize->24]&)/@Characters["123456"]]

Working with digraphs

Creating digraphs

The simplest way to create a digraph is by using FromOrderedPairs and accepting its default option Type->Directed.  (Using Type->Undirected creates an ordinary, undirected graph.)

d1=FromOrderedPairs[{ {1,2},{3,2},{3,1}}

Here's the structure of such a directed graph:

First[d1](* same as d1[[1]] *)
d1[[2]]
Last[d1]

And here is a display of this digraph:

ShowGraph[d1,VertexNumber->True]

Suppose you want to place the vertices of the digraph's drawing in particular places, for example, the locations of the vertices of a special kind of undirected graph such as a cycle, wheel, or star.  Then you may employ the following three-step process:
• create an empty graph with the vertices you want;
• use SetGraphOptions to turn on the EdgeDirection option; and
• use AddEdges to create the directed edges (in each list of two adjacent vertices you specify, the edge will be directed from the first to the second).

d2=EmptyGraph[3];ShowGraph[d2,VertexNumber->True]

d2=SetGraphOptions[d2,EdgeDirection->True]

d2=AddEdges[d2,{ {1,2},{3,2},{3,1}}]; ShowGraph[d2,VertexNumber->True]

Here's another example.

d3=Wheel[4]; 
d3=DeleteEdges[d3,Edges[d3]];
d3=SetGraphOptions[d3,EdgeDirection->True]
ShowGraph[d3,VertexNumber->True]

d3=AddEdges[d3,{{1,4},{2,1},{4,2},{4,3}}];
ShowGraph[d3,VertexNumber->True]

Displaying digraphs

Unfortunately, ShowGraph does a bad job of displaying the arrows: it puts the arrows at the ends of edges, where they may be hard to see:

ShowGraph[d1,VertexNumber->True]

To display directed graphs, you may want to use not ShowGraph, but rather the newer Mathematica 6 function GraphPlot. (Whereas ShowGraph is defined in the Combinatorica package, GraphPlot is a function defined in the Mathematica kernel, so you do not need to load any package in order to have access to it.)

GraphPlot[d1,Method->None,DirectedEdges->True,
VertexRenderingFunction->({Disk[#1,0.03],Text[#2,#1+{0.05,0.05}]}&),
EdgeRenderingFunction->({Line[#1],Arrow[#1,0.4]}&)]

While GraphPlot gives more satisfactory results, especially with digraphs, the downside is, obviously, that it is more complicated to use. But if you adopt the input cell preceding as a template, you should have little difficulty adapting it to your purposes. For example, here we include fancier formatting.

GraphPlot[d1,Method->None,DirectedEdges->True,
PlotLabel->TraditionalForm[(Subscript[D, 1])],
VertexRenderingFunction->({Black,Disk[#1,0.04],Black,Style[Text[#2,#1+{0.075,0.125}],FontFamily->"Helvetica"]}&),
EdgeRenderingFunction->({Black,Thickness[0.0035],Line[#1],Arrowheads[Large],Arrow[#1,0.4]}&),
BaseStyle->{FontSize->12}]

As with undirected graphs, you may directly create a directed graph within the body of a GraphPlot expression. Just specify the direction of each edge in the u->v items as having initial vertex u and terminal vertex v, and then include the option DirectedEdges->True.

GraphPlot[{1->2,2->3,3->4,4->1,1->3},VertexLabeling->True,DirectedEdges->True]

Adjacency matrix of a digraph

Recall our definition of the digraph d1:

d1=FromOrderedPairs[{ {1,2},{3,2},{3,1}}]

You may remove the directions on the edges like this:

MakeUndirected[d1]

ShowGraph[%]

Or, just include the option Type->Undirected in the FromOrderedPairs expression:

g1=FromOrderedPairs[{ {1,2},{3,2},{3,1}},Type->Undirected]

ToAdjacencyMatrix[d1]//MatrixForm

ToAdjacencyMatrix[g1]//MatrixForm

Notice the difference in the adjacency matrices of the directed and underlying undirected graphs.

More about displaying digraphs

Suppose you want to place the vertices of the digraph's drawing in particular places, for example, the locations of the vertices of a special kind of undirected graph such as a cycle, wheel, or star.  Then you may employ the following three-step process:
• create an empty graph with the vertices you want;
• use SetGraphOptions to turn on the EdgeDirection option; and
• use AddEdges to create the directed edges (in each list of two adjacent vertices you specify, the edge will be directed from the first to the second).

d2=EmptyGraph[3];ShowGraph[d2,VertexNumber->True]

d2=SetGraphOptions[d2,EdgeDirection->True]

d2=AddEdges[d2,{ {1,2},{3,2},{3,1}}]; ShowGraph[d2,VertexNumber->True]

Here's another example.

d3=Wheel[4]; 
d3=DeleteEdges[d3,Edges[d3]];
d3=SetGraphOptions[d3,EdgeDirection->True]
ShowGraph[d3,VertexNumber->True]

d3=AddEdges[d3,{{1,4},{2,1},{4,2},{4,3}}];
ShowGraph[d3,VertexNumber->True]

Properties of digraphs

For dealing with digraphs there are some special Combinatorica functions and additional options to functions that also apply to undirected  graphs.  For example, in addition to the ordinary degree of a vertex, we are interested in the in-degree and out-degree.  Consider again, for example, the digraph d3 from the preceding subsection.

ShowGraph[d3,VertexNumber->True]

{InDegree[d3,4],OutDegree[d3,4]}

{InDegree[d3],OutDegree[d3]}

ConnectedQ[d3]
ConnectedQ[d3,Strong]

Next consider the digraph d2 again.

ShowGraph[d2,VertexNumber->True]

EulerianQ[d2]

EulerianQ[MakeUndirected[d2]]

d4=FromOrderedPairs[{{1,2},{2,3},{3,1}}];
ShowGraph[d4]

EulerianQ[d4]

ShowGraphArray[{d2,d4}]

IsomorphicQ[d2,d4]

IsomorphicQ[MakeUndirected[d2],MakeUndirected[d4]]

Trees

In the section on creating graphs, one way to create trees was indicated: by using the Combinatorica function RandomTree.

RandomTree[10]//ShowGraph

To test whether a graph is a tree, use TreeQ.

g=Wheel[4];h=DeleteEdges[g,{{1,2},{3,4},{1,3}}];
ShowGraphArray[{g,h},VertexNumber->True]
TreeQ/@{g,h}

For displaying trees, TreePlot is a specialized version of the Mathematica kernel function GraphPlot. Just as GraphPlot does with arbitrary graphs, so TreePlot allows you to specify the tree to be displayed without actually creating any Combinatorica Graph object. The syntax is essentially the same as for GraphPlot.

TreePlot[{1->3,1->4,1->2,3->5,3->6,3->7,2->8,2->9},VertexLabeling->True]

Here's a random graph:

g=RandomGraph[12,0.5]
ShowGraph[g,VertexNumber->True]

The function MinimumSpanningTree can find a spanning tree for a connected graph.

t=MinimumSpanningTree[g];
ShowGraph[t,VertexNumber->True]

A given connected graph can have many different spanning trees. The function NumberOfSpanningTrees tells how many.

NumberOfSpanningTrees[g]

The reason for the name MinimumSpanningTree is that this function can do more than simply find a spanning tree of a connected graph.: A "weighted" graph is a graph in which each edge is assigned a certain nonnegative number as its "weight"; e.g., if the vertices represent cities, then a weight on an edge from one vertex to another could represent the distance between the two cities, or the flying time between them, etc. Then for a weighted connected graph, MinimumSpanningTree will find a spanning tree with the property that the sum of the weights of its edges is minimum. The sister function MaximumSpanningTree will do the obvious thing.

The Combinatorica function DepthFirstTraversal implements the depth-first search algorithm for finding a spanning tree of a connected graph. It takes two arguments: the graph and the starting vertex.

DepthFirstTraversal[g,1]

When the third argument Tree is used with DepthFirstTraversal, the result is the spanning tree obtained by depth-first traversal.

t=DepthFirstTraversal[g,1,Tree];
ShowGraph[t,VertexNumber->True]

Vertex colorings and edge colorings of graphs

The functions described in this section are not designed for displaying graphs but rather for finding vertex colorings and edge colorings in the graph-theoretic senses of the terms.

Vertex coloring

The function VertexColoring returns the "colors", as numbers 1, 2, …, of a graph's vertices in the same order as the vertices are listed in the underlying Graph structure.

g=CompleteGraph[3,2];ShowGraph[g,VertexNumber->True]

c =VertexColoring[g]

The result means that, for the particular vertex coloring found, the vertices 1, 2, 3, 4, 5 are given colors 1, 1, 1, 2, 2, respectively.  To actually color the vertices in accordance with that scheme, you may proceed as follows:

colors={Red,Green};
vColoring=Table[{i,VertexColor->colors[[c[[i]]]]},{i,1,Length[c]}]

ShowGraph[g,vColoring,VertexNumber->True]

The minimum number of colors needed to color the vertices of a graph is the chromatic number of the graph.  The function ChromaticNumber returns this value.

ChromaticNumber[CompleteGraph[3,2]]

The function VertexColoring does a pretty good job, but for sufficiently large and complex graphs it need not produce a minimal coloring of the vertices.  This is the case with the following example:

g=FromAdjacencyMatrix[{{0,1,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,1,1,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,1},{1,0,0,0,1,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,1,0},{1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,1,1,0},{0,0,1,0,0,1,1,0,1,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0},{1,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,0,1,1,0,1,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,1},{0,0,0,0,1,0,0,0,0,1,0,1,1,0,0,1,0,0,0,0,1,1,0,1},{0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,0},{1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,1,1,0},{0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,1,1,0,1},{0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0},{0,0,1,1,0,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0},{0,0,0,1,1,1,0,1,0,1,1,0,0,0,0,1,0,0,0,0,0,1,0,0},{0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},{1,0,0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,1,0},{1,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1},{1,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0},{0,1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,1,1,0,0,0,0,0},{0,0,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1},{0,1,0,1,0,0,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1},{0,1,1,1,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0},{0,1,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,1,1,0,0}}];
ShowGraph[g]

VertexColoring[g]

To ensure a minimal coloring—one whose number of colors is the chromatic number of the graph, include the option Algorithm->Optimum.  (Caution: using that option may dramatically increase the computational time!  Save your work before you try it.  You may need to use Evaluation ▸ Abort Evaluation if it's taking too long.)

VertexColoring[g,Algorithm->Optimum]

Chromatic polynomial

The chromatic polynomial of a graph G is a polynomial p(x) whose value at x = k is the number of vertex colorings of G that use at most k colors.

p[x_]=ChromaticPolynomial[Wheel[6],x]

Expand[p[x]]

p[{2,3,4,5}]

Since the first nonzero value of the chromatic polynomial in the preceding example is p[4], the chromatic number of the graph Wheel[6]must be 4.

Edge coloring

To find an edge coloring of a graph, use EdgeColoring.  For example:

g=PetersenGraph; 
ShowGraph[g,EdgeLabel->Range[15]]

(The edge numbers shown in the edge labels give the order in which the edges appear in the Graph object g.)

ec=EdgeColoring[g]

The result means that, for the particular edge coloring found, the edges 1, 2, 3, …, 15 are given colors 1, 2, 1, 2, 3, 1, 4, 1, 4, 2, 3, 3, 2, 3, 1, respectively.  To actually color the edges in accordance with that scheme, you may proceed as follows:

edges=Map[First,First[g]];
colors={Red,Green,Blue,Magenta};
edgeColors=Table[{edges[[i]],EdgeColor->colors[[ec[[i]]]]},{i,1,Length[edges]}];
ShowGraph[g,edgeColors]

Planarity

The function PlanarQ tests a graph for planarity.

PlanarQ[CompleteGraph[4]]

Even when a graph is planar, Combinatorica will not necessarily display the graph with a plane embedding; in other words, the geometric representation drawn by ShowGraph will use the default lane coordinates of the vertices and may therefore show edges crossing at points that are not vertices of the graph.  So actually constructing a plane embedding of a planar graph is something that requires different methods.  Question: How can it be that Combinatorica can determine whether a graph is planar and not yet actually find a plane embedding?

ShowGraph[CompleteGraph[4],VertexNumber->True]

PlanarQ[CompleteGraph[5]]
PlanarQ[CompleteGraph[3,3]]

The Petersen graph is a rather special one:

ShowGraph[PetersenGraph]

The Petersen graph is not planar:

PlanarQ[PetersenGraph]

What does Kuratowski's Theorem say about the planarity of the Petersen graph?

Acknowledgment

The author thanks several contributors to MathGroup (the Mathematica user mailing list) for assistance with some issues of displaying graphs that are created through use of the Combinatorica package but displayed by means of the Mathematica kernel function GraphPlot.