(*^

::[paletteColors = 128; 
	fontset = title, "New York", 18, L2, center, bold, nohscroll;
	fontset = subtitle, "New York", 14, L2, center, bold, nohscroll;
	fontset = subsubtitle, "New York", 14, L2, center, bold, nohscroll;
	fontset = section, "New York", 12, L2, bold, nohscroll, grayBox;
	fontset = subsection, "New York", 10, L2, bold, nohscroll, blackBox;
	fontset = subsubsection, "New York", 10, L2, bold, nohscroll, whiteBox;
	fontset = text, "New York", 9, L2, nohscroll;
	fontset = smalltext, "New York", 10, L2, nohscroll;
	fontset = input, "Courier", 10, L2, bold, nowordwrap;
	fontset = output, "Courier", 10, L2, nowordwrap;
	fontset = message, "Courier", 12, L2, R65535, nowordwrap;
	fontset = print, "Courier", 12, L2, nowordwrap;
	fontset = info, "Courier", 12, L2, nowordwrap;
	fontset = postscript, "Courier", 12, L2, nowordwrap;
	fontset = name, "Geneva", 10, L2, italic, B65535, nowordwrap, nohscroll;
	fontset = header, "Times", 10, L2;
	fontset = footer, "Times", 12, L2, center;
	fontset = help, "Geneva", 10, L2, nohscroll;
	fontset = clipboard, "New York", 12, L2;
	fontset = completions, "New York", 12, L2, nowordwrap;
	fontset = network, "Courier", 10, L2, nowordwrap;
	fontset = graphlabel, "Courier", 12, L2, nowordwrap;
	fontset = special1, "New York", 12, L2, nowordwrap;
	fontset = special2, "New York", 12, L2, center, nowordwrap;
	fontset = special3, "New York", 12, L2, right, nowordwrap;
	fontset = special4, "New York", 12, L2, nowordwrap;
	fontset = special5, "New York", 12, L2, nowordwrap;]
:[font = title; inactive; startGroup; ]
Combinatorial Mathematica
:[font = subsubtitle; inactive; ]

Steven S. Skiena
Department of Computer Science
State University of New York
Stony Brook, NY 11794

(516) 632-9026/8470
skiena@sbcs.sunysb.edu

;[s]
2:0,1;1,0;145,-1;
2:1,19,14,New York,1,14,0,0,0;1,19,14,New York,0,14,0,0,0;
:[font = text; inactive; ]
Combinatorial Mathematica is a package that comprises over 230 functions in combinatorics and graph theory.  It includes functions for constructing graphs and other combinatorial objects, computing invariants of these objects, and finally displaying them.  This notebook provides an introduction to the package by illustrating some of the things that can be done with it, and providing a complete list of functions.
;[s]
2:0,1;25,0;416,-1;
2:1,14,10,New York,0,9,0,0,0;1,14,10,New York,2,9,0,0,0;
:[font = text; inactive; ]
The best guide to Combinatorial Mathematica is the book Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, by Steven S. Skiena,  published by Addison-Wesley, 1990.   For each function in the package, the book presents the theory behind it, a complete implementation, and examples of its use.  Also, it provides related exercises and a complete reference guide.
;[s]
5:0,0;18,1;43,0;56,1;138,0;394,-1;
2:3,14,10,New York,0,9,0,0,0;2,14,10,New York,2,9,0,0,0;
:[font = text; inactive; ]
This notebook illustrates some of the things that can be done with Combinatorial Mathematica. It is not necessary to obtain the book to use the package, but it is strongly recommended.  Documentation strings for all accessible functions are included with the package, and a complete list of functions is given at the end of this document to help you get started.
;[s]
3:0,0;67,1;92,0;363,-1;
2:2,14,10,New York,0,9,0,0,0;1,14,10,New York,2,9,0,0,0;
:[font = text; inactive; ]
For further information about Combinatorial Mathematica,  and to be kept informed about new releases, please contact the author at the above address, preferably electronically.  The package is available by anonymous FTP from cs.sunysb.edu, or can be obtained on Macintosh and MS-DOS disks from Wolfram Research for a nominal fee.  For further information about the book (ISBN 0-201-50943-1) please call Addison-Wesley at (800) 447-2226.
;[s]
3:0,0;30,1;55,0;437,-1;
2:2,14,10,New York,0,9,0,0,0;1,14,10,New York,2,9,0,0,0;
:[font = input; initialization; ]
*)
<<Combinatorica.m
(*
:[font = section; inactive; startGroup; pageBreak; ]
Permutations, Subsets, Partitions, and Tableaux
:[font = text; inactive; ]
Combinatorial Mathematica provides a variety of functions to construct and compute invariants of combinatorial objects such as permutations, subsets, partitions, and Young tableaux.
;[s]
4:0,1;13,0;14,1;25,0;182,-1;
2:2,14,10,New York,0,9,0,0,0;2,14,10,New York,2,9,0,0,0;
:[font = subsection; inactive; startGroup; ]
Permutations
:[font = text; inactive; ]
Permutations can be constructed in a variety of different ways, and represent a fundamental combinatorial object useful for constructing more sophisticated objects.  Here we construct all distinct permutations of a multiset, in such a way as to avoid computing permutations more than once.
:[font = input; startGroup; ]
DistinctPermutations[{1,1,1,2,2,2}]
:[font = output; inactive; output; endGroup; ]
{{1, 1, 1, 2, 2, 2}, {1, 1, 2, 1, 2, 2}, {1, 1, 2, 2, 1, 2}, 
  {1, 1, 2, 2, 2, 1}, {1, 2, 1, 1, 2, 2}, {1, 2, 1, 2, 1, 2}, 
  {1, 2, 1, 2, 2, 1}, {1, 2, 2, 1, 1, 2}, {1, 2, 2, 1, 2, 1}, 
  {1, 2, 2, 2, 1, 1}, {2, 1, 1, 1, 2, 2}, {2, 1, 1, 2, 1, 2}, 
  {2, 1, 1, 2, 2, 1}, {2, 1, 2, 1, 1, 2}, {2, 1, 2, 1, 2, 1}, 
  {2, 1, 2, 2, 1, 1}, {2, 2, 1, 1, 1, 2}, {2, 2, 1, 1, 2, 1}, 
  {2, 2, 1, 2, 1, 1}, {2, 2, 2, 1, 1, 1}}
;[o]
{{1, 1, 1, 2, 2, 2}, {1, 1, 2, 1, 2, 2}, {1, 1, 2, 2, 1, 2}, 
 
  {1, 1, 2, 2, 2, 1}, {1, 2, 1, 1, 2, 2}, {1, 2, 1, 2, 1, 2}, 
 
  {1, 2, 1, 2, 2, 1}, {1, 2, 2, 1, 1, 2}, {1, 2, 2, 1, 2, 1}, 
 
  {1, 2, 2, 2, 1, 1}, {2, 1, 1, 1, 2, 2}, {2, 1, 1, 2, 1, 2}, 
 
  {2, 1, 1, 2, 2, 1}, {2, 1, 2, 1, 1, 2}, {2, 1, 2, 1, 2, 1}, 
 
  {2, 1, 2, 2, 1, 1}, {2, 2, 1, 1, 1, 2}, {2, 2, 1, 1, 2, 1}, 
 
  {2, 2, 1, 2, 1, 1}, {2, 2, 2, 1, 1, 1}}
:[font = text; inactive; ]
The set of all permutations defines a group, and we provide a variety of functions to explore some of its algebraic properties.  The complete set of permutations on n elements defines the symmetric group.
;[s]
3:0,0;165,1;166,0;205,-1;
2:2,14,10,New York,0,9,0,0,0;1,14,10,New York,2,9,0,0,0;
:[font = input; startGroup; ]
PermutationGroupQ[ Permutations[{1,2,3,4}] ]
:[font = output; inactive; output; endGroup; endGroup; ]
True
;[o]
True
:[font = subsection; inactive; startGroup; ]
Subsets
:[font = text; inactive; ]
The functions in this package have been designed to work together to facilitate experimentation.  This can be illustrated by constructing the Boolean lattice, the set of all subsets ordered by inclusion.   The elements of the set of all subsets can be ranked according to which elements are proper subsets of one another.
:[font = input; startGroup; ]
Subsets[4]
:[font = output; inactive; output; endGroup; ]
{{}, {1}, {1, 2}, {2}, {2, 3}, {1, 2, 3}, {1, 3}, {3}, {3, 4}, 
  {1, 3, 4}, {1, 2, 3, 4}, {2, 3, 4}, {2, 4}, {1, 2, 4}, {1, 4}, {4}}
;[o]
{{}, {1}, {1, 2}, {2}, {2, 3}, {1, 2, 3}, {1, 3}, {3}, {3, 4}, 
 
  {1, 3, 4}, {1, 2, 3, 4}, {2, 3, 4}, {2, 4}, {1, 2, 4}, {1, 4}, {4}}
:[font = text; inactive; ]
Hasse diagrams are the proper way to illustrate partial orders, and here we show the subsets of a four-element set ordered by inclusion.  MakeGraph is a useful function that converts an arbitrary binary relation to a graph which can be manipulated as any other graph.  The top vertex represents the complete set on four elements, the bottom vertex being the empty set.
;[s]
3:0,0;138,1;147,0;369,-1;
2:2,14,10,New York,0,9,0,0,0;1,14,10,New York,1,9,0,0,0;
:[font = input; startGroup; ]
ShowGraph[ HasseDiagram[ MakeGraph[ Subsets[4],
 ((Intersection[#2,#1]===#1) && (#1!=#2))&] ] ]; 
:[font = postscript; inactive; PostScript; output; endGroup; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
0.06522 1.30435 -0.65789 1.57895 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.5 0.07895 Mdot
0.23913 0.28947 Mdot
0.06522 0.5 Mdot
0.41304 0.28947 Mdot
0.23913 0.5 Mdot
0.23913 0.71053 Mdot
0.41304 0.5 Mdot
0.58696 0.28947 Mdot
0.58696 0.5 Mdot
0.41304 0.71053 Mdot
0.5 0.92105 Mdot
0.58696 0.71053 Mdot
0.76087 0.5 Mdot
0.76087 0.71053 Mdot
0.93478 0.5 Mdot
0.76087 0.28947 Mdot
0.004 setlinewidth
0.5 0.07895 moveto
0.23913 0.28947 lineto
stroke
0.5 0.07895 moveto
0.41304 0.28947 lineto
stroke
0.5 0.07895 moveto
0.58696 0.28947 lineto
stroke
0.5 0.07895 moveto
0.76087 0.28947 lineto
stroke
0.23913 0.28947 moveto
0.06522 0.5 lineto
stroke
0.23913 0.28947 moveto
0.41304 0.5 lineto
stroke
0.23913 0.28947 moveto
0.93478 0.5 lineto
stroke
0.06522 0.5 moveto
0.23913 0.71053 lineto
stroke
0.06522 0.5 moveto
0.76087 0.71053 lineto
stroke
0.41304 0.28947 moveto
0.06522 0.5 lineto
stroke
0.41304 0.28947 moveto
0.23913 0.5 lineto
stroke
0.41304 0.28947 moveto
0.76087 0.5 lineto
stroke
0.23913 0.5 moveto
0.23913 0.71053 lineto
stroke
0.23913 0.5 moveto
0.58696 0.71053 lineto
stroke
0.23913 0.71053 moveto
0.5 0.92105 lineto
stroke
0.41304 0.5 moveto
0.23913 0.71053 lineto
stroke
0.41304 0.5 moveto
0.41304 0.71053 lineto
stroke
0.58696 0.28947 moveto
0.23913 0.5 lineto
stroke
0.58696 0.28947 moveto
0.41304 0.5 lineto
stroke
0.58696 0.28947 moveto
0.58696 0.5 lineto
stroke
0.58696 0.5 moveto
0.41304 0.71053 lineto
stroke
0.58696 0.5 moveto
0.58696 0.71053 lineto
stroke
0.41304 0.71053 moveto
0.5 0.92105 lineto
stroke
0.58696 0.71053 moveto
0.5 0.92105 lineto
stroke
0.76087 0.5 moveto
0.58696 0.71053 lineto
stroke
0.76087 0.5 moveto
0.76087 0.71053 lineto
stroke
0.76087 0.71053 moveto
0.5 0.92105 lineto
stroke
0.93478 0.5 moveto
0.41304 0.71053 lineto
stroke
0.93478 0.5 moveto
0.76087 0.71053 lineto
stroke
0.76087 0.28947 moveto
0.58696 0.5 lineto
stroke
0.76087 0.28947 moveto
0.76087 0.5 lineto
stroke
0.76087 0.28947 moveto
0.93478 0.5 lineto
stroke
grestore
% End of Graphics
MathPictureEnd
:[font = subsection; inactive; startGroup; ]
Partitions
:[font = text; inactive; ]
An integer partition of n is a set of positive integers that sum up to n.  Partitions are of interest in a variety of combinatorial and number theoretic problems, and we provide the tools to construct them, count them, and display them.  Here we construct all partitions of 6 with a largest part of 3.
;[s]
5:0,0;24,1;25,0;71,1;72,0;302,-1;
2:3,14,10,New York,0,9,0,0,0;2,14,10,New York,2,9,0,0,0;
:[font = input; startGroup; ]
Partitions[6,3]
:[font = output; inactive; output; endGroup; ]
{{3, 3}, {3, 2, 1}, {3, 1, 1, 1}, {2, 2, 2}, {2, 2, 1, 1}, 
  {2, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}}
;[o]
{{3, 3}, {3, 2, 1}, {3, 1, 1, 1}, {2, 2, 2}, {2, 2, 1, 1}, 
 
  {2, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}}
:[font = text; inactive; pageBreak; ]
Functions to construct random instances of a variety of combinatorial objects are included.  The Ferrers diagram of a partition represents it as a pattern of dots, with each dot adding one to the partition.
:[font = input; startGroup; noPageBreak; ]
FerrersDiagram[ RandomPartition[50] ];
:[font = postscript; inactive; PostScript; output; endGroup; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
-0.05556 0.07937 -0.06277 0.08658 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
gsave
0.03846 setlinewidth
0.02381 0.02381 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.11039 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.19697 Mdot
0.10317 0.19697 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.28355 Mdot
0.10317 0.28355 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.37013 Mdot
0.10317 0.37013 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.45671 Mdot
0.10317 0.45671 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.54329 Mdot
0.10317 0.54329 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.62987 Mdot
0.10317 0.62987 Mdot
0.18254 0.62987 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.71645 Mdot
0.10317 0.71645 Mdot
0.18254 0.71645 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.80303 Mdot
0.10317 0.80303 Mdot
0.18254 0.80303 Mdot
0.2619 0.80303 Mdot
0.34127 0.80303 Mdot
0.42063 0.80303 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.88961 Mdot
0.10317 0.88961 Mdot
0.18254 0.88961 Mdot
0.2619 0.88961 Mdot
0.34127 0.88961 Mdot
0.42063 0.88961 Mdot
0.5 0.88961 Mdot
0.57937 0.88961 Mdot
0.65873 0.88961 Mdot
0.7381 0.88961 Mdot
0.81746 0.88961 Mdot
0.89683 0.88961 Mdot
0.97619 0.88961 Mdot
grestore
gsave
0.03846 setlinewidth
0.02381 0.97619 Mdot
0.10317 0.97619 Mdot
0.18254 0.97619 Mdot
0.2619 0.97619 Mdot
0.34127 0.97619 Mdot
0.42063 0.97619 Mdot
0.5 0.97619 Mdot
0.57937 0.97619 Mdot
0.65873 0.97619 Mdot
0.7381 0.97619 Mdot
0.81746 0.97619 Mdot
0.89683 0.97619 Mdot
0.97619 0.97619 Mdot
grestore
grestore
% End of Graphics
MathPictureEnd
:[font = subsection; inactive; startGroup; ]
Young Tableaux
:[font = text; inactive; ]
Young tableaux are arrangements of n integers whose shape can be described by a partition of n, such that each row and column is sorted.  Young tableaux are important in analyzing sorting algorithms and algebra.  Here are all tableaux of triangular shape on six elements.
;[s]
5:0,0;35,1;36,0;93,1;94,0;272,-1;
2:3,14,10,New York,0,9,0,0,0;2,14,10,New York,2,9,0,0,0;
:[font = input; startGroup; ]
Tableaux[{3,2,1}]
:[font = output; inactive; output; endGroup; ]
{{{1, 4, 6}, {2, 5}, {3}}, {{1, 3, 6}, {2, 5}, {4}}, 
  {{1, 2, 6}, {3, 5}, {4}}, {{1, 3, 6}, {2, 4}, {5}}, 
  {{1, 2, 6}, {3, 4}, {5}}, {{1, 4, 5}, {2, 6}, {3}}, 
  {{1, 3, 5}, {2, 6}, {4}}, {{1, 2, 5}, {3, 6}, {4}}, 
  {{1, 3, 4}, {2, 6}, {5}}, {{1, 2, 4}, {3, 6}, {5}}, 
  {{1, 2, 3}, {4, 6}, {5}}, {{1, 3, 5}, {2, 4}, {6}}, 
  {{1, 2, 5}, {3, 4}, {6}}, {{1, 3, 4}, {2, 5}, {6}}, 
  {{1, 2, 4}, {3, 5}, {6}}, {{1, 2, 3}, {4, 5}, {6}}}
;[o]
{{{1, 4, 6}, {2, 5}, {3}}, {{1, 3, 6}, {2, 5}, {4}}, 
 
  {{1, 2, 6}, {3, 5}, {4}}, {{1, 3, 6}, {2, 4}, {5}}, 
 
  {{1, 2, 6}, {3, 4}, {5}}, {{1, 4, 5}, {2, 6}, {3}}, 
 
  {{1, 3, 5}, {2, 6}, {4}}, {{1, 2, 5}, {3, 6}, {4}}, 
 
  {{1, 3, 4}, {2, 6}, {5}}, {{1, 2, 4}, {3, 6}, {5}}, 
 
  {{1, 2, 3}, {4, 6}, {5}}, {{1, 3, 5}, {2, 4}, {6}}, 
 
  {{1, 2, 5}, {3, 4}, {6}}, {{1, 3, 4}, {2, 5}, {6}}, 
 
  {{1, 2, 4}, {3, 5}, {6}}, {{1, 2, 3}, {4, 5}, {6}}}
:[font = text; inactive; noPageBreak; ]
The number of tableaux of a given shape grows exponentially, and can be computed using the hook length formula.
:[font = input; startGroup; ]
NumberOfTableaux[{9,8,7,6,5,4,3,2,1}]
:[font = output; inactive; output; endGroup; endGroup; endGroup; ]
273035280663535522487992320
;[o]
273035280663535522487992320
:[font = section; inactive; startGroup; ]
Generating Graphs
:[font = text; inactive; ]
Using the functions in this package, it is convenient construct a wide variety of graphs, including complete k-partite graphs, stars, wheels, trees, hypercubes, line graphs, graph products, random graphs, etc.
:[font = subsection; inactive; startGroup; ]
Circulant Graphs
:[font = text; inactive; ]
Circulant graphs have a regular structure, such that the ith row of the adjacency matrix of a circulant graph is the first row, rotated i-1 places. Complete graphs and cycles are both circulant graphs, and this function constructs a random circulant graph.
;[s]
5:0,0;57,1;58,0;136,1;139,0;257,-1;
2:3,14,10,New York,0,9,0,0,0;2,14,10,New York,2,9,0,0,0;
:[font = input; startGroup; ]
ShowGraph[ CirculantGraph[20,RandomSubset[Range[10]]] ];
:[font = postscript; inactive; PostScript; output; endGroup; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
0.04545 0.90909 0.04545 0.90909 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.9323 0.64046 Mdot
0.86773 0.76718 Mdot
0.76718 0.86773 Mdot
0.64046 0.9323 Mdot
0.5 0.95455 Mdot
0.35954 0.9323 Mdot
0.23282 0.86773 Mdot
0.13227 0.76718 Mdot
0.0677 0.64046 Mdot
0.04545 0.5 Mdot
0.0677 0.35954 Mdot
0.13227 0.23282 Mdot
0.23282 0.13227 Mdot
0.35954 0.0677 Mdot
0.5 0.04545 Mdot
0.64046 0.0677 Mdot
0.76718 0.13227 Mdot
0.86773 0.23282 Mdot
0.9323 0.35954 Mdot
0.95455 0.5 Mdot
0.004 setlinewidth
0.9323 0.64046 moveto
0.76718 0.86773 lineto
stroke
0.9323 0.64046 moveto
0.5 0.95455 lineto
stroke
0.9323 0.64046 moveto
0.35954 0.9323 lineto
stroke
0.9323 0.64046 moveto
0.23282 0.86773 lineto
stroke
0.9323 0.64046 moveto
0.13227 0.76718 lineto
stroke
0.9323 0.64046 moveto
0.0677 0.64046 lineto
stroke
0.9323 0.64046 moveto
0.0677 0.35954 lineto
stroke
0.9323 0.64046 moveto
0.23282 0.13227 lineto
stroke
0.9323 0.64046 moveto
0.35954 0.0677 lineto
stroke
0.9323 0.64046 moveto
0.5 0.04545 lineto
stroke
0.9323 0.64046 moveto
0.64046 0.0677 lineto
stroke
0.9323 0.64046 moveto
0.76718 0.13227 lineto
stroke
0.9323 0.64046 moveto
0.9323 0.35954 lineto
stroke
0.86773 0.76718 moveto
0.64046 0.9323 lineto
stroke
0.86773 0.76718 moveto
0.35954 0.9323 lineto
stroke
0.86773 0.76718 moveto
0.23282 0.86773 lineto
stroke
0.86773 0.76718 moveto
0.13227 0.76718 lineto
stroke
0.86773 0.76718 moveto
0.0677 0.64046 lineto
stroke
0.86773 0.76718 moveto
0.04545 0.5 lineto
stroke
0.86773 0.76718 moveto
0.13227 0.23282 lineto
stroke
0.86773 0.76718 moveto
0.35954 0.0677 lineto
stroke
0.86773 0.76718 moveto
0.5 0.04545 lineto
stroke
0.86773 0.76718 moveto
0.64046 0.0677 lineto
stroke
0.86773 0.76718 moveto
0.76718 0.13227 lineto
stroke
0.86773 0.76718 moveto
0.86773 0.23282 lineto
stroke
0.86773 0.76718 moveto
0.95455 0.5 lineto
stroke
0.76718 0.86773 moveto
0.9323 0.64046 lineto
stroke
0.76718 0.86773 moveto
0.5 0.95455 lineto
stroke
0.76718 0.86773 moveto
0.23282 0.86773 lineto
stroke
0.76718 0.86773 moveto
0.13227 0.76718 lineto
stroke
0.76718 0.86773 moveto
0.0677 0.64046 lineto
stroke
0.76718 0.86773 moveto
0.04545 0.5 lineto
stroke
0.76718 0.86773 moveto
0.0677 0.35954 lineto
stroke
0.76718 0.86773 moveto
0.23282 0.13227 lineto
stroke
0.76718 0.86773 moveto
0.5 0.04545 lineto
stroke
0.76718 0.86773 moveto
0.64046 0.0677 lineto
stroke
0.76718 0.86773 moveto
0.76718 0.13227 lineto
stroke
0.76718 0.86773 moveto
0.86773 0.23282 lineto
stroke
0.76718 0.86773 moveto
0.9323 0.35954 lineto
stroke
0.64046 0.9323 moveto
0.86773 0.76718 lineto
stroke
0.64046 0.9323 moveto
0.35954 0.9323 lineto
stroke
0.64046 0.9323 moveto
0.13227 0.76718 lineto
stroke
0.64046 0.9323 moveto
0.0677 0.64046 lineto
stroke
0.64046 0.9323 moveto
0.04545 0.5 lineto
stroke
0.64046 0.9323 moveto
0.0677 0.35954 lineto
stroke
0.64046 0.9323 moveto
0.13227 0.23282 lineto
stroke
0.64046 0.9323 moveto
0.35954 0.0677 lineto
stroke
0.64046 0.9323 moveto
0.64046 0.0677 lineto
stroke
0.64046 0.9323 moveto
0.76718 0.13227 lineto
stroke
0.64046 0.9323 moveto
0.86773 0.23282 lineto
stroke
0.64046 0.9323 moveto
0.9323 0.35954 lineto
stroke
0.64046 0.9323 moveto
0.95455 0.5 lineto
stroke
0.5 0.95455 moveto
0.9323 0.64046 lineto
stroke
0.5 0.95455 moveto
0.76718 0.86773 lineto
stroke
0.5 0.95455 moveto
0.23282 0.86773 lineto
stroke
0.5 0.95455 moveto
0.0677 0.64046 lineto
stroke
0.5 0.95455 moveto
0.04545 0.5 lineto
stroke
0.5 0.95455 moveto
0.0677 0.35954 lineto
stroke
0.5 0.95455 moveto
0.13227 0.23282 lineto
stroke
0.5 0.95455 moveto
0.23282 0.13227 lineto
stroke
0.5 0.95455 moveto
0.5 0.04545 lineto
stroke
0.5 0.95455 moveto
0.76718 0.13227 lineto
stroke
0.5 0.95455 moveto
0.86773 0.23282 lineto
stroke
0.5 0.95455 moveto
0.9323 0.35954 lineto
stroke
0.5 0.95455 moveto
0.95455 0.5 lineto
stroke
0.35954 0.9323 moveto
0.9323 0.64046 lineto
stroke
0.35954 0.9323 moveto
0.86773 0.76718 lineto
stroke
0.35954 0.9323 moveto
0.64046 0.9323 lineto
stroke
0.35954 0.9323 moveto
0.13227 0.76718 lineto
stroke
0.35954 0.9323 moveto
0.04545 0.5 lineto
stroke
0.35954 0.9323 moveto
0.0677 0.35954 lineto
stroke
0.35954 0.9323 moveto
0.13227 0.23282 lineto
stroke
0.35954 0.9323 moveto
0.23282 0.13227 lineto
stroke
0.35954 0.9323 moveto
0.35954 0.0677 lineto
stroke
0.35954 0.9323 moveto
0.64046 0.0677 lineto
stroke
0.35954 0.9323 moveto
0.86773 0.23282 lineto
stroke
0.35954 0.9323 moveto
0.9323 0.35954 lineto
stroke
0.35954 0.9323 moveto
0.95455 0.5 lineto
stroke
0.23282 0.86773 moveto
0.9323 0.64046 lineto
stroke
0.23282 0.86773 moveto
0.86773 0.76718 lineto
stroke
0.23282 0.86773 moveto
0.76718 0.86773 lineto
stroke
0.23282 0.86773 moveto
0.5 0.95455 lineto
stroke
0.23282 0.86773 moveto
0.0677 0.64046 lineto
stroke
0.23282 0.86773 moveto
0.0677 0.35954 lineto
stroke
0.23282 0.86773 moveto
0.13227 0.23282 lineto
stroke
0.23282 0.86773 moveto
0.23282 0.13227 lineto
stroke
0.23282 0.86773 moveto
0.35954 0.0677 lineto
stroke
0.23282 0.86773 moveto
0.5 0.04545 lineto
stroke
0.23282 0.86773 moveto
0.76718 0.13227 lineto
stroke
0.23282 0.86773 moveto
0.9323 0.35954 lineto
stroke
0.23282 0.86773 moveto
0.95455 0.5 lineto
stroke
0.13227 0.76718 moveto
0.9323 0.64046 lineto
stroke
0.13227 0.76718 moveto
0.86773 0.76718 lineto
stroke
0.13227 0.76718 moveto
0.76718 0.86773 lineto
stroke
0.13227 0.76718 moveto
0.64046 0.9323 lineto
stroke
0.13227 0.76718 moveto
0.35954 0.9323 lineto
stroke
0.13227 0.76718 moveto
0.04545 0.5 lineto
stroke
0.13227 0.76718 moveto
0.13227 0.23282 lineto
stroke
0.13227 0.76718 moveto
0.23282 0.13227 lineto
stroke
0.13227 0.76718 moveto
0.35954 0.0677 lineto
stroke
0.13227 0.76718 moveto
0.5 0.04545 lineto
stroke
0.13227 0.76718 moveto
0.64046 0.0677 lineto
stroke
0.13227 0.76718 moveto
0.86773 0.23282 lineto
stroke
0.13227 0.76718 moveto
0.95455 0.5 lineto
stroke
0.0677 0.64046 moveto
0.9323 0.64046 lineto
stroke
0.0677 0.64046 moveto
0.86773 0.76718 lineto
stroke
0.0677 0.64046 moveto
0.76718 0.86773 lineto
stroke
0.0677 0.64046 moveto
0.64046 0.9323 lineto
stroke
0.0677 0.64046 moveto
0.5 0.95455 lineto
stroke
0.0677 0.64046 moveto
0.23282 0.86773 lineto
stroke
0.0677 0.64046 moveto
0.0677 0.35954 lineto
stroke
0.0677 0.64046 moveto
0.23282 0.13227 lineto
stroke
0.0677 0.64046 moveto
0.35954 0.0677 lineto
stroke
0.0677 0.64046 moveto
0.5 0.04545 lineto
stroke
0.0677 0.64046 moveto
0.64046 0.0677 lineto
stroke
0.0677 0.64046 moveto
0.76718 0.13227 lineto
stroke
0.0677 0.64046 moveto
0.9323 0.35954 lineto
stroke
0.04545 0.5 moveto
0.86773 0.76718 lineto
stroke
0.04545 0.5 moveto
0.76718 0.86773 lineto
stroke
0.04545 0.5 moveto
0.64046 0.9323 lineto
stroke
0.04545 0.5 moveto
0.5 0.95455 lineto
stroke
0.04545 0.5 moveto
0.35954 0.9323 lineto
stroke
0.04545 0.5 moveto
0.13227 0.76718 lineto
stroke
0.04545 0.5 moveto
0.13227 0.23282 lineto
stroke
0.04545 0.5 moveto
0.35954 0.0677 lineto
stroke
0.04545 0.5 moveto
0.5 0.04545 lineto
stroke
0.04545 0.5 moveto
0.64046 0.0677 lineto
stroke
0.04545 0.5 moveto
0.76718 0.13227 lineto
stroke
0.04545 0.5 moveto
0.86773 0.23282 lineto
stroke
0.04545 0.5 moveto
0.95455 0.5 lineto
stroke
0.0677 0.35954 moveto
0.9323 0.64046 lineto
stroke
0.0677 0.35954 moveto
0.76718 0.86773 lineto
stroke
0.0677 0.35954 moveto
0.64046 0.9323 lineto
stroke
0.0677 0.35954 moveto
0.5 0.95455 lineto
stroke
0.0677 0.35954 moveto
0.35954 0.9323 lineto
stroke
0.0677 0.35954 moveto
0.23282 0.86773 lineto
stroke
0.0677 0.35954 moveto
0.0677 0.64046 lineto
stroke
0.0677 0.35954 moveto
0.23282 0.13227 lineto
stroke
0.0677 0.35954 moveto
0.5 0.04545 lineto
stroke
0.0677 0.35954 moveto
0.64046 0.0677 lineto
stroke
0.0677 0.35954 moveto
0.76718 0.13227 lineto
stroke
0.0677 0.35954 moveto
0.86773 0.23282 lineto
stroke
0.0677 0.35954 moveto
0.9323 0.35954 lineto
stroke
0.13227 0.23282 moveto
0.86773 0.76718 lineto
stroke
0.13227 0.23282 moveto
0.64046 0.9323 lineto
stroke
0.13227 0.23282 moveto
0.5 0.95455 lineto
stroke
0.13227 0.23282 moveto
0.35954 0.9323 lineto
stroke
0.13227 0.23282 moveto
0.23282 0.86773 lineto
stroke
0.13227 0.23282 moveto
0.13227 0.76718 lineto
stroke
0.13227 0.23282 moveto
0.04545 0.5 lineto
stroke
0.13227 0.23282 moveto
0.35954 0.0677 lineto
stroke
0.13227 0.23282 moveto
0.64046 0.0677 lineto
stroke
0.13227 0.23282 moveto
0.76718 0.13227 lineto
stroke
0.13227 0.23282 moveto
0.86773 0.23282 lineto
stroke
0.13227 0.23282 moveto
0.9323 0.35954 lineto
stroke
0.13227 0.23282 moveto
0.95455 0.5 lineto
stroke
0.23282 0.13227 moveto
0.9323 0.64046 lineto
stroke
0.23282 0.13227 moveto
0.76718 0.86773 lineto
stroke
0.23282 0.13227 moveto
0.5 0.95455 lineto
stroke
0.23282 0.13227 moveto
0.35954 0.9323 lineto
stroke
0.23282 0.13227 moveto
0.23282 0.86773 lineto
stroke
0.23282 0.13227 moveto
0.13227 0.76718 lineto
stroke
0.23282 0.13227 moveto
0.0677 0.64046 lineto
stroke
0.23282 0.13227 moveto
0.0677 0.35954 lineto
stroke
0.23282 0.13227 moveto
0.5 0.04545 lineto
stroke
0.23282 0.13227 moveto
0.76718 0.13227 lineto
stroke
0.23282 0.13227 moveto
0.86773 0.23282 lineto
stroke
0.23282 0.13227 moveto
0.9323 0.35954 lineto
stroke
0.23282 0.13227 moveto
0.95455 0.5 lineto
stroke
0.35954 0.0677 moveto
0.9323 0.64046 lineto
stroke
0.35954 0.0677 moveto
0.86773 0.76718 lineto
stroke
0.35954 0.0677 moveto
0.64046 0.9323 lineto
stroke
0.35954 0.0677 moveto
0.35954 0.9323 lineto
stroke
0.35954 0.0677 moveto
0.23282 0.86773 lineto
stroke
0.35954 0.0677 moveto
0.13227 0.76718 lineto
stroke
0.35954 0.0677 moveto
0.0677 0.64046 lineto
stroke
0.35954 0.0677 moveto
0.04545 0.5 lineto
stroke
0.35954 0.0677 moveto
0.13227 0.23282 lineto
stroke
0.35954 0.0677 moveto
0.64046 0.0677 lineto
stroke
0.35954 0.0677 moveto
0.86773 0.23282 lineto
stroke
0.35954 0.0677 moveto
0.9323 0.35954 lineto
stroke
0.35954 0.0677 moveto
0.95455 0.5 lineto
stroke
0.5 0.04545 moveto
0.9323 0.64046 lineto
stroke
0.5 0.04545 moveto
0.86773 0.76718 lineto
stroke
0.5 0.04545 moveto
0.76718 0.86773 lineto
stroke
0.5 0.04545 moveto
0.5 0.95455 lineto
stroke
0.5 0.04545 moveto
0.23282 0.86773 lineto
stroke
0.5 0.04545 moveto
0.13227 0.76718 lineto
stroke
0.5 0.04545 moveto
0.0677 0.64046 lineto
stroke
0.5 0.04545 moveto
0.04545 0.5 lineto
stroke
0.5 0.04545 moveto
0.0677 0.35954 lineto
stroke
0.5 0.04545 moveto
0.23282 0.13227 lineto
stroke
0.5 0.04545 moveto
0.76718 0.13227 lineto
stroke
0.5 0.04545 moveto
0.9323 0.35954 lineto
stroke
0.5 0.04545 moveto
0.95455 0.5 lineto
stroke
0.64046 0.0677 moveto
0.9323 0.64046 lineto
stroke
0.64046 0.0677 moveto
0.86773 0.76718 lineto
stroke
0.64046 0.0677 moveto
0.76718 0.86773 lineto
stroke
0.64046 0.0677 moveto
0.64046 0.9323 lineto
stroke
0.64046 0.0677 moveto
0.35954 0.9323 lineto
stroke
0.64046 0.0677 moveto
0.13227 0.76718 lineto
stroke
0.64046 0.0677 moveto
0.0677 0.64046 lineto
stroke
0.64046 0.0677 moveto
0.04545 0.5 lineto
stroke
0.64046 0.0677 moveto
0.0677 0.35954 lineto
stroke
0.64046 0.0677 moveto
0.13227 0.23282 lineto
stroke
0.64046 0.0677 moveto
0.35954 0.0677 lineto
stroke
0.64046 0.0677 moveto
0.86773 0.23282 lineto
stroke
0.64046 0.0677 moveto
0.95455 0.5 lineto
stroke
0.76718 0.13227 moveto
0.9323 0.64046 lineto
stroke
0.76718 0.13227 moveto
0.86773 0.76718 lineto
stroke
0.76718 0.13227 moveto
0.76718 0.86773 lineto
stroke
0.76718 0.13227 moveto
0.64046 0.9323 lineto
stroke
0.76718 0.13227 moveto
0.5 0.95455 lineto
stroke
0.76718 0.13227 moveto
0.23282 0.86773 lineto
stroke
0.76718 0.13227 moveto
0.0677 0.64046 lineto
stroke
0.76718 0.13227 moveto
0.04545 0.5 lineto
stroke
0.76718 0.13227 moveto
0.0677 0.35954 lineto
stroke
0.76718 0.13227 moveto
0.13227 0.23282 lineto
stroke
0.76718 0.13227 moveto
0.23282 0.13227 lineto
stroke
0.76718 0.13227 moveto
0.5 0.04545 lineto
stroke
0.76718 0.13227 moveto
0.9323 0.35954 lineto
stroke
0.86773 0.23282 moveto
0.86773 0.76718 lineto
stroke
0.86773 0.23282 moveto
0.76718 0.86773 lineto
stroke
0.86773 0.23282 moveto
0.64046 0.9323 lineto
stroke
0.86773 0.23282 moveto
0.5 0.95455 lineto
stroke
0.86773 0.23282 moveto
0.35954 0.9323 lineto
stroke
0.86773 0.23282 moveto
0.13227 0.76718 lineto
stroke
0.86773 0.23282 moveto
0.04545 0.5 lineto
stroke
0.86773 0.23282 moveto
0.0677 0.35954 lineto
stroke
0.86773 0.23282 moveto
0.13227 0.23282 lineto
stroke
0.86773 0.23282 moveto
0.23282 0.13227 lineto
stroke
0.86773 0.23282 moveto
0.35954 0.0677 lineto
stroke
0.86773 0.23282 moveto
0.64046 0.0677 lineto
stroke
0.86773 0.23282 moveto
0.95455 0.5 lineto
stroke
0.9323 0.35954 moveto
0.9323 0.64046 lineto
stroke
0.9323 0.35954 moveto
0.76718 0.86773 lineto
stroke
0.9323 0.35954 moveto
0.64046 0.9323 lineto
stroke
0.9323 0.35954 moveto
0.5 0.95455 lineto
stroke
0.9323 0.35954 moveto
0.35954 0.9323 lineto
stroke
0.9323 0.35954 moveto
0.23282 0.86773 lineto
stroke
0.9323 0.35954 moveto
0.0677 0.64046 lineto
stroke
0.9323 0.35954 moveto
0.0677 0.35954 lineto
stroke
0.9323 0.35954 moveto
0.13227 0.23282 lineto
stroke
0.9323 0.35954 moveto
0.23282 0.13227 lineto
stroke
0.9323 0.35954 moveto
0.35954 0.0677 lineto
stroke
0.9323 0.35954 moveto
0.5 0.04545 lineto
stroke
0.9323 0.35954 moveto
0.76718 0.13227 lineto
stroke
0.95455 0.5 moveto
0.86773 0.76718 lineto
stroke
0.95455 0.5 moveto
0.64046 0.9323 lineto
stroke
0.95455 0.5 moveto
0.5 0.95455 lineto
stroke
0.95455 0.5 moveto
0.35954 0.9323 lineto
stroke
0.95455 0.5 moveto
0.23282 0.86773 lineto
stroke
0.95455 0.5 moveto
0.13227 0.76718 lineto
stroke
0.95455 0.5 moveto
0.04545 0.5 lineto
stroke
0.95455 0.5 moveto
0.13227 0.23282 lineto
stroke
0.95455 0.5 moveto
0.23282 0.13227 lineto
stroke
0.95455 0.5 moveto
0.35954 0.0677 lineto
stroke
0.95455 0.5 moveto
0.5 0.04545 lineto
stroke
0.95455 0.5 moveto
0.64046 0.0677 lineto
stroke
0.95455 0.5 moveto
0.86773 0.23282 lineto
stroke
grestore
% End of Graphics
MathPictureEnd
:[font = subsection; inactive; startGroup; ]
Graph Products
:[font = text; inactive; ]
Graph products lend themselves to interesting drawings.  The products are commutative but the embeddings are not, so GraphProduct[K[5],K[3]] yields a different picture but an isomorphic graph.
;[s]
3:0,0;117,1;140,0;193,-1;
2:2,14,10,New York,0,9,0,0,0;1,14,10,New York,1,9,0,0,0;
:[font = input; startGroup; pageBreak; ]
ShowGraph[ GraphProduct[ K[3], K[5] ] ];
:[font = postscript; inactive; PostScript; output; endGroup; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
0.04587 0.9174 0.01782 0.93541 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.04587 0.66264 Mdot
0.04587 0.51696 Mdot
0.1696 0.5898 Mdot
0.1957 0.19245 Mdot
0.1957 0.04677 Mdot
0.31944 0.11961 Mdot
0.68056 0.19245 Mdot
0.68056 0.04677 Mdot
0.8043 0.11961 Mdot
0.8304 0.66264 Mdot
0.8304 0.51696 Mdot
0.95413 0.5898 Mdot
0.43813 0.95323 Mdot
0.43813 0.80755 Mdot
0.56187 0.88039 Mdot
0.004 setlinewidth
0.04587 0.66264 moveto
0.04587 0.51696 lineto
stroke
0.04587 0.66264 moveto
0.1696 0.5898 lineto
stroke
0.04587 0.66264 moveto
0.1957 0.19245 lineto
stroke
0.04587 0.66264 moveto
0.68056 0.19245 lineto
stroke
0.04587 0.66264 moveto
0.8304 0.66264 lineto
stroke
0.04587 0.66264 moveto
0.43813 0.95323 lineto
stroke
0.04587 0.51696 moveto
0.04587 0.66264 lineto
stroke
0.04587 0.51696 moveto
0.1696 0.5898 lineto
stroke
0.04587 0.51696 moveto
0.1957 0.04677 lineto
stroke
0.04587 0.51696 moveto
0.68056 0.04677 lineto
stroke
0.04587 0.51696 moveto
0.8304 0.51696 lineto
stroke
0.04587 0.51696 moveto
0.43813 0.80755 lineto
stroke
0.1696 0.5898 moveto
0.04587 0.66264 lineto
stroke
0.1696 0.5898 moveto
0.04587 0.51696 lineto
stroke
0.1696 0.5898 moveto
0.31944 0.11961 lineto
stroke
0.1696 0.5898 moveto
0.8043 0.11961 lineto
stroke
0.1696 0.5898 moveto
0.95413 0.5898 lineto
stroke
0.1696 0.5898 moveto
0.56187 0.88039 lineto
stroke
0.1957 0.19245 moveto
0.04587 0.66264 lineto
stroke
0.1957 0.19245 moveto
0.1957 0.04677 lineto
stroke
0.1957 0.19245 moveto
0.31944 0.11961 lineto
stroke
0.1957 0.19245 moveto
0.68056 0.19245 lineto
stroke
0.1957 0.19245 moveto
0.8304 0.66264 lineto
stroke
0.1957 0.19245 moveto
0.43813 0.95323 lineto
stroke
0.1957 0.04677 moveto
0.04587 0.51696 lineto
stroke
0.1957 0.04677 moveto
0.1957 0.19245 lineto
stroke
0.1957 0.04677 moveto
0.31944 0.11961 lineto
stroke
0.1957 0.04677 moveto
0.68056 0.04677 lineto
stroke
0.1957 0.04677 moveto
0.8304 0.51696 lineto
stroke
0.1957 0.04677 moveto
0.43813 0.80755 lineto
stroke
0.31944 0.11961 moveto
0.1696 0.5898 lineto
stroke
0.31944 0.11961 moveto
0.1957 0.19245 lineto
stroke
0.31944 0.11961 moveto
0.1957 0.04677 lineto
stroke
0.31944 0.11961 moveto
0.8043 0.11961 lineto
stroke
0.31944 0.11961 moveto
0.95413 0.5898 lineto
stroke
0.31944 0.11961 moveto
0.56187 0.88039 lineto
stroke
0.68056 0.19245 moveto
0.04587 0.66264 lineto
stroke
0.68056 0.19245 moveto
0.1957 0.19245 lineto
stroke
0.68056 0.19245 moveto
0.68056 0.04677 lineto
stroke
0.68056 0.19245 moveto
0.8043 0.11961 lineto
stroke
0.68056 0.19245 moveto
0.8304 0.66264 lineto
stroke
0.68056 0.19245 moveto
0.43813 0.95323 lineto
stroke
0.68056 0.04677 moveto
0.04587 0.51696 lineto
stroke
0.68056 0.04677 moveto
0.1957 0.04677 lineto
stroke
0.68056 0.04677 moveto
0.68056 0.19245 lineto
stroke
0.68056 0.04677 moveto
0.8043 0.11961 lineto
stroke
0.68056 0.04677 moveto
0.8304 0.51696 lineto
stroke
0.68056 0.04677 moveto
0.43813 0.80755 lineto
stroke
0.8043 0.11961 moveto
0.1696 0.5898 lineto
stroke
0.8043 0.11961 moveto
0.31944 0.11961 lineto
stroke
0.8043 0.11961 moveto
0.68056 0.19245 lineto
stroke
0.8043 0.11961 moveto
0.68056 0.04677 lineto
stroke
0.8043 0.11961 moveto
0.95413 0.5898 lineto
stroke
0.8043 0.11961 moveto
0.56187 0.88039 lineto
stroke
0.8304 0.66264 moveto
0.04587 0.66264 lineto
stroke
0.8304 0.66264 moveto
0.1957 0.19245 lineto
stroke
0.8304 0.66264 moveto
0.68056 0.19245 lineto
stroke
0.8304 0.66264 moveto
0.8304 0.51696 lineto
stroke
0.8304 0.66264 moveto
0.95413 0.5898 lineto
stroke
0.8304 0.66264 moveto
0.43813 0.95323 lineto
stroke
0.8304 0.51696 moveto
0.04587 0.51696 lineto
stroke
0.8304 0.51696 moveto
0.1957 0.04677 lineto
stroke
0.8304 0.51696 moveto
0.68056 0.04677 lineto
stroke
0.8304 0.51696 moveto
0.8304 0.66264 lineto
stroke
0.8304 0.51696 moveto
0.95413 0.5898 lineto
stroke
0.8304 0.51696 moveto
0.43813 0.80755 lineto
stroke
0.95413 0.5898 moveto
0.1696 0.5898 lineto
stroke
0.95413 0.5898 moveto
0.31944 0.11961 lineto
stroke
0.95413 0.5898 moveto
0.8043 0.11961 lineto
stroke
0.95413 0.5898 moveto
0.8304 0.66264 lineto
stroke
0.95413 0.5898 moveto
0.8304 0.51696 lineto
stroke
0.95413 0.5898 moveto
0.56187 0.88039 lineto
stroke
0.43813 0.95323 moveto
0.04587 0.66264 lineto
stroke
0.43813 0.95323 moveto
0.1957 0.19245 lineto
stroke
0.43813 0.95323 moveto
0.68056 0.19245 lineto
stroke
0.43813 0.95323 moveto
0.8304 0.66264 lineto
stroke
0.43813 0.95323 moveto
0.43813 0.80755 lineto
stroke
0.43813 0.95323 moveto
0.56187 0.88039 lineto
stroke
0.43813 0.80755 moveto
0.04587 0.51696 lineto
stroke
0.43813 0.80755 moveto
0.1957 0.04677 lineto
stroke
0.43813 0.80755 moveto
0.68056 0.04677 lineto
stroke
0.43813 0.80755 moveto
0.8304 0.51696 lineto
stroke
0.43813 0.80755 moveto
0.43813 0.95323 lineto
stroke
0.43813 0.80755 moveto
0.56187 0.88039 lineto
stroke
0.56187 0.88039 moveto
0.1696 0.5898 lineto
stroke
0.56187 0.88039 moveto
0.31944 0.11961 lineto
stroke
0.56187 0.88039 moveto
0.8043 0.11961 lineto
stroke
0.56187 0.88039 moveto
0.95413 0.5898 lineto
stroke
0.56187 0.88039 moveto
0.43813 0.95323 lineto
stroke
0.56187 0.88039 moveto
0.43813 0.80755 lineto
stroke
grestore
% End of Graphics
MathPictureEnd
:[font = subsection; inactive; startGroup; ]
Hypercubes
:[font = text; inactive; ]
Hypercubes are recursively defined, where the n-cube is the product of K[2] and the (n-1)-cube.  The 4-cube is the easiest four-dimensional object to visualize.
;[s]
7:0,0;46,1;47,0;71,2;75,0;84,1;89,0;161,-1;
3:4,14,10,New York,0,9,0,0,0;2,14,10,New York,2,9,0,0,0;1,14,10,New York,1,9,0,0,0;
:[font = input; startGroup; ]
ShowGraph[ Hypercube[4] ];
:[font = postscript; inactive; PostScript; output; endGroup; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
0.04545 0.90909 0.04545 0.90909 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.04545 0.52837 Mdot
0.1044 0.41269 Mdot
0.22008 0.47163 Mdot
0.16114 0.58731 Mdot
0.41269 0.16114 Mdot
0.47163 0.04545 Mdot
0.58731 0.1044 Mdot
0.52837 0.22008 Mdot
0.77992 0.52837 Mdot
0.83886 0.41269 Mdot
0.95455 0.47163 Mdot
0.8956 0.58731 Mdot
0.41269 0.8956 Mdot
0.47163 0.77992 Mdot
0.58731 0.83886 Mdot
0.52837 0.95455 Mdot
0.004 setlinewidth
0.04545 0.52837 moveto
0.1044 0.41269 lineto
stroke
0.04545 0.52837 moveto
0.16114 0.58731 lineto
stroke
0.04545 0.52837 moveto
0.41269 0.16114 lineto
stroke
0.04545 0.52837 moveto
0.41269 0.8956 lineto
stroke
0.1044 0.41269 moveto
0.04545 0.52837 lineto
stroke
0.1044 0.41269 moveto
0.22008 0.47163 lineto
stroke
0.1044 0.41269 moveto
0.47163 0.04545 lineto
stroke
0.1044 0.41269 moveto
0.47163 0.77992 lineto
stroke
0.22008 0.47163 moveto
0.1044 0.41269 lineto
stroke
0.22008 0.47163 moveto
0.16114 0.58731 lineto
stroke
0.22008 0.47163 moveto
0.58731 0.1044 lineto
stroke
0.22008 0.47163 moveto
0.58731 0.83886 lineto
stroke
0.16114 0.58731 moveto
0.04545 0.52837 lineto
stroke
0.16114 0.58731 moveto
0.22008 0.47163 lineto
stroke
0.16114 0.58731 moveto
0.52837 0.22008 lineto
stroke
0.16114 0.58731 moveto
0.52837 0.95455 lineto
stroke
0.41269 0.16114 moveto
0.04545 0.52837 lineto
stroke
0.41269 0.16114 moveto
0.47163 0.04545 lineto
stroke
0.41269 0.16114 moveto
0.52837 0.22008 lineto
stroke
0.41269 0.16114 moveto
0.77992 0.52837 lineto
stroke
0.47163 0.04545 moveto
0.1044 0.41269 lineto
stroke
0.47163 0.04545 moveto
0.41269 0.16114 lineto
stroke
0.47163 0.04545 moveto
0.58731 0.1044 lineto
stroke
0.47163 0.04545 moveto
0.83886 0.41269 lineto
stroke
0.58731 0.1044 moveto
0.22008 0.47163 lineto
stroke
0.58731 0.1044 moveto
0.47163 0.04545 lineto
stroke
0.58731 0.1044 moveto
0.52837 0.22008 lineto
stroke
0.58731 0.1044 moveto
0.95455 0.47163 lineto
stroke
0.52837 0.22008 moveto
0.16114 0.58731 lineto
stroke
0.52837 0.22008 moveto
0.41269 0.16114 lineto
stroke
0.52837 0.22008 moveto
0.58731 0.1044 lineto
stroke
0.52837 0.22008 moveto
0.8956 0.58731 lineto
stroke
0.77992 0.52837 moveto
0.41269 0.16114 lineto
stroke
0.77992 0.52837 moveto
0.83886 0.41269 lineto
stroke
0.77992 0.52837 moveto
0.8956 0.58731 lineto
stroke
0.77992 0.52837 moveto
0.41269 0.8956 lineto
stroke
0.83886 0.41269 moveto
0.47163 0.04545 lineto
stroke
0.83886 0.41269 moveto
0.77992 0.52837 lineto
stroke
0.83886 0.41269 moveto
0.95455 0.47163 lineto
stroke
0.83886 0.41269 moveto
0.47163 0.77992 lineto
stroke
0.95455 0.47163 moveto
0.58731 0.1044 lineto
stroke
0.95455 0.47163 moveto
0.83886 0.41269 lineto
stroke
0.95455 0.47163 moveto
0.8956 0.58731 lineto
stroke
0.95455 0.47163 moveto
0.58731 0.83886 lineto
stroke
0.8956 0.58731 moveto
0.52837 0.22008 lineto
stroke
0.8956 0.58731 moveto
0.77992 0.52837 lineto
stroke
0.8956 0.58731 moveto
0.95455 0.47163 lineto
stroke
0.8956 0.58731 moveto
0.52837 0.95455 lineto
stroke
0.41269 0.8956 moveto
0.04545 0.52837 lineto
stroke
0.41269 0.8956 moveto
0.77992 0.52837 lineto
stroke
0.41269 0.8956 moveto
0.47163 0.77992 lineto
stroke
0.41269 0.8956 moveto
0.52837 0.95455 lineto
stroke
0.47163 0.77992 moveto
0.1044 0.41269 lineto
stroke
0.47163 0.77992 moveto
0.83886 0.41269 lineto
stroke
0.47163 0.77992 moveto
0.41269 0.8956 lineto
stroke
0.47163 0.77992 moveto
0.58731 0.83886 lineto
stroke
0.58731 0.83886 moveto
0.22008 0.47163 lineto
stroke
0.58731 0.83886 moveto
0.95455 0.47163 lineto
stroke
0.58731 0.83886 moveto
0.47163 0.77992 lineto
stroke
0.58731 0.83886 moveto
0.52837 0.95455 lineto
stroke
0.52837 0.95455 moveto
0.16114 0.58731 lineto
stroke
0.52837 0.95455 moveto
0.8956 0.58731 lineto
stroke
0.52837 0.95455 moveto
0.41269 0.8956 lineto
stroke
0.52837 0.95455 moveto
0.58731 0.83886 lineto
stroke
grestore
% End of Graphics
MathPictureEnd
:[font = subsection; inactive; startGroup; ]
Trees
:[font = text; inactive; ]
Trees are connected graphs without cycles, and are the simplest interesting class of graphs.  Because of their structure, random labeled trees can be constructed in a mathematically precise way.
:[font = input; startGroup; pageBreak; ]
ShowGraph[ RandomTree[10] ];
:[font = postscript; inactive; PostScript; output; endGroup; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
0.04545 0.90909 0.04545 0.90909 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.5 0.5 Mdot
0.65152 0.65152 Mdot
0.80303 0.80303 Mdot
0.19697 0.19697 Mdot
0.80303 0.19697 Mdot
0.34848 0.65152 Mdot
0.34848 0.34848 Mdot
0.65152 0.34848 Mdot
0.04545 0.04545 Mdot
0.95455 0.95455 Mdot
0.004 setlinewidth
0.5 0.5 moveto
0.65152 0.65152 lineto
stroke
0.5 0.5 moveto
0.34848 0.65152 lineto
stroke
0.5 0.5 moveto
0.34848 0.34848 lineto
stroke
0.5 0.5 moveto
0.65152 0.34848 lineto
stroke
0.65152 0.65152 moveto
0.5 0.5 lineto
stroke
0.65152 0.65152 moveto
0.80303 0.80303 lineto
stroke
0.80303 0.80303 moveto
0.65152 0.65152 lineto
stroke
0.80303 0.80303 moveto
0.95455 0.95455 lineto
stroke
0.19697 0.19697 moveto
0.34848 0.34848 lineto
stroke
0.19697 0.19697 moveto
0.04545 0.04545 lineto
stroke
0.80303 0.19697 moveto
0.65152 0.34848 lineto
stroke
0.34848 0.65152 moveto
0.5 0.5 lineto
stroke
0.34848 0.34848 moveto
0.5 0.5 lineto
stroke
0.34848 0.34848 moveto
0.19697 0.19697 lineto
stroke
0.65152 0.34848 moveto
0.5 0.5 lineto
stroke
0.65152 0.34848 moveto
0.80303 0.19697 lineto
stroke
0.04545 0.04545 moveto
0.19697 0.19697 lineto
stroke
0.95455 0.95455 moveto
0.80303 0.80303 lineto
stroke
grestore
% End of Graphics
MathPictureEnd
:[font = input; endGroup; ]

:[font = section; inactive; startGroup; ]
Properties of Graphs
:[font = text; inactive; ]
The graphs we have seen are not just pretty to look at.  They provide data for studying the properties of graphs.  We have included a wide variety functions to compute graph invariants, and thus determine which graphs have what properties.
:[font = subsection; inactive; startGroup; ]
Connectivity
:[font = text; inactive; ]
Most interesting graphs tend to be connected, meaning they come in one piece.  There are different notions of connectivity for directed and undirected graphs, as well as measures of how connected a graph is.  Functions for computing the vertex and edge connectivity of a graph, and extracting biconnected and strongly/weakly connected components of a graph are included.
:[font = text; inactive; ]
An undirected graph is oriented by assigning a direction to each edge, such that the resulting directed graph is strongly connected.  In a strongly connected graph, there is a directed path between any pair of vertices.  Thus in any city, either the roads define a strongly connected graph or there are some cars that can't get home!
:[font = input; startGroup; pageBreak; ]
ShowGraph[ OrientGraph[ GridGraph[3,3] ], Directed ];
:[font = postscript; inactive; PostScript; output; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
0.04545 0.90909 0.04545 0.90909 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.04545 0.04545 Mdot
0.5 0.04545 Mdot
0.95455 0.04545 Mdot
0.04545 0.5 Mdot
0.5 0.5 Mdot
0.95455 0.5 Mdot
0.04545 0.95455 Mdot
0.5 0.95455 Mdot
0.95455 0.95455 Mdot
0.004 setlinewidth
0.04545 0.04545 moveto
0.5 0.04545 lineto
stroke
0.5 0.04545 moveto
0.95455 0.04545 lineto
stroke
0.95455 0.04545 moveto
0.95455 0.5 lineto
stroke
0.04545 0.5 moveto
0.04545 0.04545 lineto
stroke
0.04545 0.5 moveto
0.5 0.5 lineto
stroke
0.5 0.5 moveto
0.5 0.04545 lineto
stroke
0.5 0.5 moveto
0.5 0.95455 lineto
stroke
0.95455 0.5 moveto
0.5 0.5 lineto
stroke
0.04545 0.95455 moveto
0.04545 0.5 lineto
stroke
0.5 0.95455 moveto
0.04545 0.95455 lineto
stroke
0.5 0.95455 moveto
0.95455 0.95455 lineto
stroke
0.95455 0.95455 moveto
0.95455 0.5 lineto
stroke
0.5 0.04545 moveto
0.45455 0.06818 lineto
0.45455 0.02273 lineto
fill
0.95455 0.04545 moveto
0.90909 0.06818 lineto
0.90909 0.02273 lineto
fill
0.95455 0.5 moveto
0.93182 0.45455 lineto
0.97727 0.45455 lineto
fill
0.04545 0.04545 moveto
0.06818 0.09091 lineto
0.02273 0.09091 lineto
fill
0.5 0.5 moveto
0.45455 0.52273 lineto
0.45455 0.47727 lineto
fill
0.5 0.04545 moveto
0.52273 0.09091 lineto
0.47727 0.09091 lineto
fill
0.5 0.95455 moveto
0.47727 0.90909 lineto
0.52273 0.90909 lineto
fill
0.5 0.5 moveto
0.54545 0.47727 lineto
0.54545 0.52273 lineto
fill
0.04545 0.5 moveto
0.06818 0.54545 lineto
0.02273 0.54545 lineto
fill
0.04545 0.95455 moveto
0.09091 0.93182 lineto
0.09091 0.97727 lineto
fill
0.95455 0.95455 moveto
0.90909 0.97727 lineto
0.90909 0.93182 lineto
fill
0.95455 0.5 moveto
0.97727 0.54545 lineto
0.93182 0.54545 lineto
fill
grestore
% End of Graphics
MathPictureEnd
:[font = text; inactive; ]
Since an oriented graph is strongly connected, it contains exactly one strongly connected component.
:[font = input; startGroup; ]
StronglyConnectedComponents[ OrientGraph[GridGraph[3,3]] ]
:[font = output; inactive; output; endGroup; endGroup; ]
{{9, 4, 7, 8, 5, 6, 3, 2, 1}}
;[o]
{{9, 4, 7, 8, 5, 6, 3, 2, 1}}
:[font = subsection; inactive; startGroup; ]
Eulerian and Hamiltonian Cycles
:[font = text; inactive; ]
An Eulerian cycle of a graph visits each edge exactly once before returning to its starting point.  A Hamiltonian cycle of a graph visits each vertex exactly once before returning to its starting point.  Despite these similar definitions, Eulerian graphs are well-characterized, but Hamiltonian graphs are not.
:[font = input; startGroup; pageBreak; ]
ShowLabeledGraph[ K[4,4] ];
:[font = postscript; inactive; PostScript; output; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
-1.72222 2.59259 0.05224 1.04478 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.12963 0.05224 Mdot
0.12963 0.35075 Mdot
0.12963 0.64925 Mdot
0.12963 0.94776 Mdot
0.87037 0.05224 Mdot
0.87037 0.35075 Mdot
0.87037 0.64925 Mdot
0.87037 0.94776 Mdot
0.004 setlinewidth
0.12963 0.05224 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.05224 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.05224 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.05224 moveto
0.87037 0.94776 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.94776 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.94776 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.94776 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.94776 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.94776 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.94776 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.94776 lineto
stroke
0.12963 0.05224 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.05224 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.05224 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.05224 moveto
0.87037 0.94776 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.35075 moveto
0.87037 0.94776 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.64925 moveto
0.87037 0.94776 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.05224 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.35075 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.64925 lineto
stroke
0.12963 0.94776 moveto
0.87037 0.94776 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.05224 moveto
0.12963 0.94776 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.35075 moveto
0.12963 0.94776 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.64925 moveto
0.12963 0.94776 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.05224 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.35075 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.64925 lineto
stroke
0.87037 0.94776 moveto
0.12963 0.94776 lineto
stroke
0 setgray
[(1)] 0.05185 0.0209 0 1 Mshowa
0 setgray
[(2)] 0.05185 0.3194 0 1 Mshowa
0 setgray
[(3)] 0.05185 0.61791 0 1 Mshowa
0 setgray
[(4)] 0.05185 0.91642 0 1 Mshowa
0 setgray
[(5)] 0.79259 0.0209 0 1 Mshowa
0 setgray
[(6)] 0.79259 0.3194 0 1 Mshowa
0 setgray
[(7)] 0.79259 0.61791 0 1 Mshowa
0 setgray
[(8)] 0.79259 0.91642 0 1 Mshowa
grestore
% End of Graphics
MathPictureEnd
:[font = text; inactive; ]
A graph is Eulerian if and only if every vertex is of even degree.
:[font = input; startGroup; ]
EulerianCycle[ K[4,4] ]
:[font = output; inactive; output; endGroup; ]
{7, 2, 8, 1, 5, 4, 6, 3, 7, 4, 8, 3, 5, 2, 6, 1, 7}
;[o]
{7, 2, 8, 1, 5, 4, 6, 3, 7, 4, 8, 3, 5, 2, 6, 1, 7}
:[font = text; inactive; ]
Complete bipartite graphs are Hamiltonian if and only if both stages contain the same number of vertices.
:[font = input; startGroup; ]
HamiltonianCycle[ K[4,4] ]
:[font = output; inactive; output; endGroup; endGroup; ]
{1, 5, 2, 6, 3, 7, 4, 8, 1}
;[o]
{1, 5, 2, 6, 3, 7, 4, 8, 1}
:[font = subsection; inactive; startGroup; ]
Minimum Spanning Trees
:[font = text; inactive; ]
Combinatorial Mathematica includes a variety of functions for working with weighted graphs.  A minimum spanning tree of a weighted graph is a connected subgraph such that the sum of the weights of the edges of the subgraph is minimized.  Since an unweighted graph like K[6,6,6] can be considered as having edges of equal weight, any spanning tree is a minimum spanning tree.
;[s]
4:0,1;25,0;269,2;277,0;375,-1;
3:2,14,10,New York,0,9,0,0,0;1,14,10,New York,2,9,0,0,0;1,14,10,New York,1,9,0,0,0;
:[font = input; startGroup; pageBreak; ]
ShowGraph[ MinimumSpanningTree[ K[6,6,6] ] ];
:[font = postscript; inactive; PostScript; output; endGroup; pictureLeft = 37; pictureWidth = 193; pictureHeight = 193; preserveAspect; ]
%!
%%Creator: Mathematica
%%AspectRatio: 1 
MathPictureStart
% Scaling calculations
-1.26471 2.15686 0.04955 0.99099 [
[ 0 0 0 0 ]
[ 1 1 0 0 ]
] MathScale
% Start of Graphics
1 setlinecap
1 setlinejoin
newpath
%%Object: Graphics
[ ] 0 setdash
0 setgray
gsave
gsave
grestore
grestore
0 0 moveto
1 0 lineto
1 1 lineto
0 1 lineto
closepath
clip
newpath
0 setgray
gsave
0.025 setlinewidth
0.10784 0.04955 Mdot
0.10784 0.22973 Mdot
0.10784 0.40991 Mdot
0.10784 0.59009 Mdot
0.10784 0.77027 Mdot
0.10784 0.95045 Mdot
0.5 0.04955 Mdot
0.5 0.22973 Mdot
0.5 0.40991 Mdot
0.5 0.59009 Mdot
0.5 0.77027 Mdot
0.5 0.95045 Mdot
0.89216 0.04955 Mdot
0.89216 0.22973 Mdot
0.89216 0.40991 Mdot
0.89216 0.59009 Mdot
0.89216 0.77027 Mdot
0.89216 0.95045 Mdot
0.004 setlinewidth
0.10784 0.04955 moveto
0.5 0.04955 lineto
stroke
0.10784 0.04955 moveto
0.5 0.22973 lineto
stroke
0.10784 0.04955 moveto
0.5 0.40991 lineto
stroke
0.10784 0.04955 moveto
0.5 0.59009 lineto
stroke
0.10784 0.04955 moveto
0.5 0.77027 lineto
stroke
0.10784 0.04955 moveto
0.5 0.95045 lineto
stroke
0.10784 0.04955 moveto
0.89216 0.04955 lineto
stroke
0.10784 0.04955 moveto
0.89216 0.22973 lineto
stroke
0.10784 0.04955 moveto
0.89216 0.40991 lineto
stroke
0.10784 0.04955 moveto
0.89216 0.59009 lineto
stroke
0.10784 0.04955 moveto
0.89216 0.77027 lineto
stroke
0.10784 0.04955 moveto
0.89216 0.95045 lineto
stroke
0.10784 0.22973 moveto
0.5 0.04955 lineto
stroke
0.10784 0.40991 moveto
0.5 0.04955 lineto
stroke
0.10784 0.59009 moveto
0.5 0.04955 lineto
stroke
0.10784 0.77027 moveto
0.5 0.04955 lineto
stroke
0.10784 0.95045 moveto
0.5 0.04955 lineto
stroke
0.5 0.04955 moveto
0.10784 0.04955 lineto
stroke
0.5 0.04955 moveto
0.10784 0.22973 lineto
stroke
0.5 0.04955 moveto
0.10784 0.40991 lineto
stroke
0.5 0.04955 moveto
0.10784 0.59009 lineto
stroke
0.5 0.04955 moveto
0.10784 0.77027 lineto
stroke
0.5 0.04955 moveto
0.10784 0.95045 lineto
stroke
0.5 0.22973 moveto
0.10784 0.04955 lineto
stroke
0.5 0.40991 moveto
0.10784 0.04955 lineto
stroke
0.5 0.59009 moveto
0.10784 0.04955 lineto
stroke
0.5 0.77027 moveto
0.10784 0.04955 lineto
stroke
0.5 0.95045 moveto
0.10784 0.04955 lineto
stroke
0.89216 0.04955 moveto
0.10784 0.04955 lineto
stroke
0.89216 0.22973 moveto
0.10784 0.04955 lineto
stroke
0.89216 0.40991 moveto
0.10784 0.04955 lineto
stroke
0.89216 0.59009 moveto
0.10784 0.04955 lineto
stroke
0.89216 0.77027 moveto
0.10784 0.04955 lineto
stroke
0.89216 0.95045 moveto
0.10784 0.04955 lineto
stroke
grestore
% End of Graphics
MathPictureEnd
:[font = text; inactive; ]
Using matrix techniques, it is possible to determine the number of spanning trees of a graph without explicitly counting them.
:[font = input; startGroup; ]
NumberOfSpanningTrees[ K[6,6,6] ]
:[font = output; inactive; output; endGroup; endGroup; endGroup; ]
277326388342554624
;[o]
277326388342554624
:[font = section; inactive; startGroup; ]
List of Functions
:[font = text; inactive; ]
Since each accessible function has an associated documentation string, it would be redundant to include them here.  To see what a function does, simply use the Mathematica help facility.
;[s]
3:0,0;160,1;171,0;187,-1;
2:2,14,10,New York,0,9,0,0,0;1,14,10,New York,2,9,0,0,0;
:[font = text; inactive; ]
All functions starting with a particular prefix can be obtained by using wildcards.
:[font = input; startGroup; ]
?Graph*
:[font = info; inactive; endGroup; ]
Graph             GraphJoin         GraphicQ
GraphCenter       GraphPower        Graphics
GraphComplement   GraphProduct      Graphics3D
GraphDifference   GraphSum          GraphicsFont
GraphIntersection GraphUnion        GraphicsLeading
:[font = text; inactive; ]
The documentation string can be obtained by using a single question mark.
:[font = input; startGroup; ]
?GraphProduct
:[font = info; inactive; endGroup; ]
GraphProduct[g,h] constructs the product of graphs g and h.
:[font = text; inactive; ]
The complete implementation can be obtained by using two question marks, although the implementations are much more readable in the book.
:[font = input; startGroup; pageBreak; ]
??GraphDifference
:[font = info; inactive; endGroup; ]
GraphDifference[g,h] constructs the graph resulting from subtracting
   the adjacency matrix of graph g from that of graph h.
Attributes[GraphDifference] = {Protected}
GraphDifference/: 
 
  GraphDifference[Combinatorica`private`g1_Graph, 
 
    Combinatorica`private`g2_Graph] := 
 
   Graph[Edges[Combinatorica`private`g1] - 
 
      Edges[Combinatorica`private`g2], 
 
     Vertices[Combinatorica`private`g1]] /; 
 
    V[Combinatorica`private`g1] == V[Combinatorica`private`g2]
:[font = text; inactive; ]
Here is a complete list of all the functions in the package:
:[font = input; startGroup; ]
?Combinatorica`*
:[font = info; inactive; endGroup; endGroup; endGroup; ]
AcyclicQ                     MakeSimple
AddEdge                      MakeUndirected
AddVertex                    MaximalMatching
AllPairsShortestPath         MaximumAntichain
ArticulationVertices         MaximumClique
Automorphisms                MaximumIndependentSet
Backtrack                    MaximumSpanningTree
BiconnectedComponents        MinimumChainPartition
BiconnectedQ                 MinimumChangePermutations
BinarySearch                 MinimumSpanningTree
BinarySubsets                MinimumVertexCover
BipartiteMatching            MultiplicationTable
BipartiteQ                   NetworkFlow
BreadthFirstTraversal        NetworkFlowEdges
Bridges                      NextComposition
CartesianProduct             NextKSubset
CatalanNumber                NextPartition
ChangeEdges                  NextPermutation
ChangeVertices               NextSubset
ChromaticNumber              NextTableau
ChromaticPolynomial          NormalizeVertices
CirculantGraph               NthPair
CircularVertices             NthPermutation
CliqueQ                      NthSubset
CodeToLabeledTree            NumberOfCompositions
Cofactor                     NumberOfDerangements
CompleteQ                    NumberOfInvolutions
Compositions                 NumberOfPartitions
ConnectedComponents          NumberOfPermutationsByCycles
ConnectedQ                   NumberOfSpanningTrees
ConstructTableau             NumberOfTableaux
Contract                     OrientGraph
CostOfPath                   PartialOrderQ
Cycle                        PartitionQ
DeBruijnSequence             Partitions
DegreeSequence               Path
DeleteCycle                  PathConditionGraph
DeleteEdge                   PerfectQ
DeleteFromTableau            PermutationGroupQ
DeleteVertex                 PermutationQ
DepthFirstTraversal          Permute
DerangementQ                 PlanarQ
Derangements                 PointsAndLines
Diameter                     Polya
Dijkstra                     PseudographQ
DilateVertices               RadialEmbedding
Directed                     Radius
DistinctPermutations         RandomComposition
Distribution                 RandomGraph
DurfeeSquare                 RandomHeap
Eccentricity                 RandomKSubset
Edge                         RandomPartition
EdgeChromaticNumber          RandomPermutation
EdgeColoring                 RandomPermutation1
EdgeConnectivity             RandomPermutation2
Edges                        RandomSubset
Element                      RandomTableau
EmptyGraph                   RandomTree
EmptyQ                       RandomVertices
EncroachingListSet           RankGraph
EquivalenceClasses           RankPermutation
EquivalenceRelationQ         RankSubset
Equivalences                 RankedEmbedding
Eulerian                     ReadGraph
EulerianCycle                RealizeDegreeSequence
EulerianQ                    RegularGraph
ExactRandomGraph             RegularQ
ExpandGraph                  RemoveSelfLoops
ExtractCycles                RevealCycles
FerrersDiagram               RootedEmbedding
FindCycle                    RotateVertices
FindSet                      Runs
FirstLexicographicTableau    SamenessRelation
FromAdjacencyLists           SelectionSort
FromCycles                   SelfComplementaryQ
FromInversionVector          ShakeGraph
FromOrderedPairs             ShortestPath
FromUnorderedPairs           ShortestPathSpanningTree
FunctionalGraph              ShowGraph
Girth                        ShowLabeledGraph
Graph                        SignaturePermutation
GraphCenter                  SimpleQ
GraphComplement              Spectrum
GraphDifference              SpringEmbedding
GraphIntersection            StableMarriage
GraphJoin                    Star
GraphPower                   StirlingFirst
GraphProduct                 StirlingSecond
GraphSum                     Strings
GraphUnion                   StronglyConnectedComponents
GraphicQ                     Subsets
GrayCode                     TableauClasses
GridGraph                    TableauQ
HamiltonianCycle             Tableaux
HamiltonianQ                 TableauxToPermutation
Harary                       ToAdjacencyLists
HasseDiagram                 ToCycles
HeapSort                     ToInversionVector
Heapify                      ToOrderedPairs
HideCycles                   ToUnorderedPairs
Hypercube                    TopologicalSort
IdenticalQ                   TransitiveClosure
IncidenceMatrix              TransitiveQ
IndependentSetQ              TransitiveReduction
Index                        TranslateVertices
InduceSubgraph               TransposePartition
InitializeUnionFind          TransposeTableau
InsertIntoTableau            TravelingSalesman
IntervalGraph                TravelingSalesmanBounds
InversePermutation           TreeQ
Inversions                   TriangleInequalityQ
InvolutionQ                  Turan
IsomorphicQ                  TwoColoring
Isomorphism                  Undirected
IsomorphismQ                 UndirectedQ
Josephus                     UnionSet
K                            UnweightedQ
KSubsets                     V
LabeledTreeToCode            VertexColoring
LastLexicographicTableau     VertexConnectivity
LexicographicPermutations    VertexCoverQ
LexicographicSubsets         Vertices
LineGraph                    WeaklyConnectedComponents
LongestIncreasingSubsequence Wheel
M                            WriteGraph
MakeGraph
^*)