A Database of Graphs in <i>Combinatorica</i> Format

A Database of Graphs in Combinatorica Format

This page contains several collection of important classes of graphs, all converted to the graph format used by Combinatorica, a package for teaching and research in discrete mathematics, particularly combinatorics and graph theory. See our associated book: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by Sriram Pemmaraju and Steven Skiena, Cambridge University Press, 2003 for more information about Combinatorica.

These graphs can be used to test conjectures, by explictly testing whether a given property holds on all small trees, bipartite graphs, etc. Experiments with Random labeled graphs are typically easy to construct, but experiments with them are typically wasteful because isomorphic copies can be repeatedly generated, and unconvincing because they do not systematically look for all possible counter-examples. These graph collections represent complete sets of interesting unlabeled graphs, and permit typically testing all relevant graphs up to a non-trivial number of vertices. For example, the animation above cycles through all 106 unlabeled trees on 10 vertices; by comparison, there are 100,000,00 labeled trees on 10 vertices!

These graphs are converted to Combinatorica format from the originals made available in the compact but unprintable g6 format on Gordon Royle's website. He deserves great thanks for making them available. Larger instances of many graph classes are available on his site. The conversion from g6 format was done using conversion software developed by King Larry Mak at Stony Brook. Graph databases available include

All of these files have been collected into a single 6MB gzipped tarfile for convenient downloading. A Database of Graphs in <i>Combinatorica</i> Format

A Database of Graphs in Combinatorica Format

This page contains several collection of important classes of graphs, all converted to the graph format used by Combinatorica, a package for teaching and research in discrete mathematics, particularly combinatorics and graph theory.

These graphs can be used to test conjectures, by explictly testing whether a given property holds on all small trees, bipartite graphs, etc. Experiments with Random labeled graphs are typically easy to construct, but experiments with them are typically wasteful because isomorphic copies can be repeatedly generated, and unconvincing because they do not systematically look for all possible counter-examples. These graph collections represent complete sets of interesting unlabeled graphs, and permit typically testing all relevant graphs up to a non-trivial number of vertices. For example, the animation above cycles through all 106 unlabeled trees on 10 vertices; by comparison, there are 100,000,00 labeled trees on 10 vertices!

These graphs are converted to Combinatorica format from the originals made available in the compact but unprintable g6 format on Gordon Royle's website. He deserves great thanks for making them available. Larger instances of many graph classes are available on his site. The conversion from g6 format was done using conversion software developed by King Larry Mak at Stony Brook. Graph databases available include




Bipartite Graphs


Vertices1234567
21
31
4 1 2
5 1 4
6 1 6 10
7 1 9 34
8 1 12 76 93
9 1 16 155 558
10 1 20 290 1824 1897



Trees


Vertices Number
1 1
2 1
3 1
4 2
5 3
6 6
7 11
8 23
9 47
10 106
11 235
12 551
13 1301
14 3159



Vertex-critical graphs


VerticesNumber
41
52
61
710
817
9370



Edge-critical graphs


EdgeNumber
41
52
61
75
89
947
10338



Type-2 Edge Colorable Graphs (Vizing's theorem)


VerticesNumber
54
63
732
867
9930



Cubic graphs


Verticesgirth>=3>=5>=6>=7
85000
1019100
1285200
14509910
1640604910
184130145550
205104895783320
227319447909383850
24117940535162047975741
262094480864314785841812273
28404971380114624501462450121
302094480864432757568122090544546



Snarks


VerticesCyc-con>=4>=5>=6
1011
1200
1400
1600
1820
2061
22202
24382
2628010
282900751



Transitive graphs


VerticesTransitiveCaleyConnected TransitiveConnected CayleyConnected Non-Cayley
1 1 1 0 1 1 0
2 2 2 0 1 1 0
3 2 2 0 1 1 0
4 4 4 0 2 2 0
5 3 3 0 2 2 0
6 8 8 0 5 5 0
7 4 4 0 3 3 0
8 14 14 0 10 10 0
9 9 9 0 7 7 0
10 22 20 2 18 16 2
11 8 8 0 7 7 0
12 74 74 0 64 64 0
13 14 14 0 13 13 0
14 56 56 0 51 51 0
15 48 44 4 44 40 4
16 286 278 8 272 264 8
17 36 36 0 35 35 0
18 380 376 4 365 361 4
19 60 60 0 59 59 0
20 1214 1132 82 1190 1110 80
21 240 240 0 235 235 0
22 816 816 0 807 807 0
23 188 188 0 187 187 0
24 15506 15394 112 15422 15310 112
25 464 464 0 461 461 0
26 4236 4104 132 4221 4089 132
27 1434 1434 0 1425 1425 0
28 25850 25784 66 25792 25726 66
29 1182 1182 0 1181 1181 0
30 46308 45184 1124 46236 45118 1118
31 2192 2192 0 2191 2191 0



Cubic Transitive Graphs

VerticesPrime FactorizationSymmetricCayleyNon-CayleyTotal
68 2, 2, 17 0 11 1 12
70 2, 5, 7 0 11 0 11
72 2, 2, 2, 3, 3 1 36 1 37
74 2, 37 1 8 1 9
76 2, 2, 19 0 11 0 11
78 2, 3, 13 1 14 0 14
80 2, 2, 2, 2, 5 1 29 4 33
82 2, 41 0 8 1 9
84 2, 2, 3, 7 1 27 3 30
86 2, 43 1 9 0 9
88 2, 2, 2, 11 0 16 1 17
90 2, 3, 3, 5 1 18 3 21
92 2, 2, 23 0 13 0 13
94 2, 47 0 9 0 9
96 2, 2, 2, 2, 2, 3 2 90 ? ?
98 2, 7, 7 2 13 0 13
100 2, 2, 5, 5 0 23 2 25
102 2, 3, 17 1 15 1 16
104 2, 2, 2, 13 1 ? ? 22
106 2, 53 0 10 1 11
108 2, 2, 3, 3, 3 1 ? ? 42
110 2, 5, 11 1 19 0 19
112 2, 2, 2, 2, 7 3 ? ? 38
114 2, 3, 19 1 18 0 18
116 2, 2, 29 0 17 1 18
118 2, 59 0 11 0 11
120 2, 2, 2, 3, 5 2 ? ? ?
122 2, 61 1 12 1 13
124 2, 2, 31 0 17 0 17
126 2, 3, 3, 7 1 ? ? 26
128 2, 2, 2, 2, 2, 2, 2 2 82 1 83
130 2, 5, 13 0 17 2 19
132 2, 2, 3, 11 0 ? ? 35
134 2, 67 1 13 0 13
136 2, 2, 2, 17 0 ? ? 28
138 2, 3, 23 0 19 0 19
140 2, 2, 5, 7 0 ? ? ?
142 2, 71 0 13 0 13
144 2, 2, 2, 2, 3, 3 2 ? ? ?
146 2, 73 1 14 1 15
148 2, 2, 37 0 21 1 22
150 2, 3, 5, 5 1 ? ? 28
152 2, 2, 2, 19 1 ? ? 27
154 2, 7, 11 0 19 0 19
156 2, 2, 3, 13 0 ? ? 46
158 2, 79 1 15 0 15
160 2, 2, 2, 2, 2, 5 0 ? ? ?
162 2, 3, 3, 3, 3 3 ? ? ?
164 2, 2, 41 0 23 1 24
166 2, 83 0 15 0 15
168 2, 2, 2, 3, 7 6 ? ? ?
170 2, 5, 17 0 21 2 23
172 2, 2, 43 0 23 0 23
174 2, 3, 29 0 23 0 23
176 2, 2, 2, 2, 11 0 ? ? ?
178 2, 89 0 16 1 17
180 2, 2, 3, 3, 5 0 ? ? ?
182 2, 7, 13 4 23 2 25
184 2, 2, 2, 23 0 ? ? 31
186 2, 3, 31 1 26 0 26
188 2, 2, 47 0 25 0 25
190 2, 5, 19 0 23 0 23
192 2, 2, 2, 2, 2, 2, 3 3 ? ? ?
194 2, 97 1 18 1 19
196 2, 2, 7, 7 0 ? ? 35
198 2, 3, 3, 11 0 ? ? ?
200 2, 2, 2, 5, 5 1 ? ? 61
202 2, 101 0 18 1 19
204 2, 2, 3, 17 1 ? ? 53
206 2, 103 1 19 0 19
208 2, 2, 2, 2, 13 1 ? ? ?
210 2, 3, 5, 7 0 43 ? ?
212 2, 2, 53 0 29 ? 30
214 2, 107 0 19 0 19
216 2, 2, 2, 3, 3, 3 3 ? ? ?
218 2, 109 1 20 1 21
220 2, 2, 5, 11 3 ? ? ?
222 2, 3, 37 1 30 0 30
224 2, 2, 2, 2, 2, 7 3 ? ? ?
226 2, 113 0 20 1 21
228 2, 2, 3, 19 0 ? ? 57
230 2, 5, 23 0 27 0 27
232 2, 2, 2, 29 0 ? ? 40
234 2, 3, 3, 13 2 ? ? ?
236 2, 2, 59 0 31 0 31
238 2, 7, 17 0 27 ? ?
240 2, 2, 2, 2, 3, 5 3 ? ? ?
242 2, 11, 11 1 25 0 25
244 2, 2, 61 0 33 1 34
246 2, 3, 41 0 31 0 31
248 2, 2, 2, 31 1 ? ? 41
250 2, 5, 5, 5 1 ? ? 37
252 2, 2, 3, 3, 7 0 ? ? ?
254 2, 127 1 23 0 23
256 2, 2, 2, 2, 2, 2, 2, 2 4 ? ? 284
258 2, 3, 43 1 34 0 34


Bipartite Graphs


Vertices1234567
21
31
4 1 2
5 1 4
6 1 6 10
7 1 9 34
8 1 12 76 93
9 1 16 155 558
10 1 20 290 1824 1897



Trees


Vertices Number
1 1
2 1
3 1
4 2
5 3
6 6
7 11
8 23
9 47
10 106
11 235
12 551
13 1301
14 3159



Vertex-critical graphs


VerticesNumber
41
52
61
710
817
9370
105530



Edge-critical graphs


EdgeNumber
41
52
61
75
89
947
10338
115649



Type-2 Edge Colorable Graphs (Vizing's theorem)


VerticesNumber
54
63
732
867
9930



Cubic graphs


Verticesgirth>=3>=5>=6>=7
85000
1019100
1285200
14509910
1640604910
184130145550
205104895783320
227319447909383850
24117940535162047975741
262094480864314785841812273
28404971380114624501462450121
302094480864432757568122090544546



Snarks


VerticesCyc-con>=4>=5>=6
1011
1200
1400
1600
1820
2061
22202
24382
2628010
282900751



Transitive graphs


VerticesTransitiveCaleyConnected TransitiveConnected CayleyConnected Non-Cayley
1 1 1 0 1 1 0
2 2 2 0 1 1 0
3 2 2 0 1 1 0
4 4 4 0 2 2 0
5 3 3 0 2 2 0
6 8 8 0 5 5 0
7 4 4 0 3 3 0
8 14 14 0 10 10 0
9 9 9 0 7 7 0
10 22 20 2 18 16 2
11 8 8 0 7 7 0
12 74 74 0 64 64 0
13 14 14 0 13 13 0
14 56 56 0 51 51 0
15 48 44 4 44 40 4
16 286 278 8 272 264 8
17 36 36 0 35 35 0
18 380 376 4 365 361 4
19 60 60 0 59 59 0
20 1214 1132 82 1190 1110 80
21 240 240 0 235 235 0
22 816 816 0 807 807 0
23 188 188 0 187 187 0
24 15506 15394 112 15422 15310 112
25 464 464 0 461 461 0
26 4236 4104 132 4221 4089 132
27 1434 1434 0 1425 1425 0
28 25850 25784 66 25792 25726 66
29 1182 1182 0 1181 1181 0
30 46308 45184 1124 46236 45118 1118
31 2192 2192 0 2191 2191 0



Cubic Transitive Graphs

VerticesPrime FactorizationSymmetricCayleyNon-CayleyTotal
68 2, 2, 17 0 11 1 12
70 2, 5, 7 0 11 0 11
72 2, 2, 2, 3, 3 1 36 1 37
74 2, 37 1 8 1 9
76 2, 2, 19 0 11 0 11
78 2, 3, 13 1 14 0 14
80 2, 2, 2, 2, 5 1 29 4 33
82 2, 41 0 8 1 9
84 2, 2, 3, 7 1 27 3 30
86 2, 43 1 9 0 9
88 2, 2, 2, 11 0 16 1 17
90 2, 3, 3, 5 1 18 3 21
92 2, 2, 23 0 13 0 13
94 2, 47 0 9 0 9
96 2, 2, 2, 2, 2, 3 2 90 ? ?
98 2, 7, 7 2 13 0 13
100 2, 2, 5, 5 0 23 2 25
102 2, 3, 17 1 15 1 16
104 2, 2, 2, 13 1 ? ? 22
106 2, 53 0 10 1 11
108 2, 2, 3, 3, 3 1 ? ? 42
110 2, 5, 11 1 19 0 19
112 2, 2, 2, 2, 7 3 ? ? 38
114 2, 3, 19 1 18 0 18
116 2, 2, 29 0 17 1 18
118 2, 59 0 11 0 11
120 2, 2, 2, 3, 5 2 ? ? ?
122 2, 61 1 12 1 13
124 2, 2, 31 0 17 0 17
126 2, 3, 3, 7 1 ? ? 26
128 2, 2, 2, 2, 2, 2, 2 2 82 1 83
130 2, 5, 13 0 17 2 19
132 2, 2, 3, 11 0 ? ? 35
134 2, 67 1 13 0 13
136 2, 2, 2, 17 0 ? ? 28
138 2, 3, 23 0 19 0 19
140 2, 2, 5, 7 0 ? ? ?
142 2, 71 0 13 0 13
144 2, 2, 2, 2, 3, 3 2 ? ? ?
146 2, 73 1 14 1 15
148 2, 2, 37 0 21 1 22
150 2, 3, 5, 5 1 ? ? 28
152 2, 2, 2, 19 1 ? ? 27
154 2, 7, 11 0 19 0 19
156 2, 2, 3, 13 0 ? ? 46
158 2, 79 1 15 0 15
160 2, 2, 2, 2, 2, 5 0 ? ? ?
162 2, 3, 3, 3, 3 3 ? ? ?
164 2, 2, 41 0 23 1 24
166 2, 83 0 15 0 15
168 2, 2, 2, 3, 7 6 ? ? ?
170 2, 5, 17 0 21 2 23
172 2, 2, 43 0 23 0 23
174 2, 3, 29 0 23 0 23
176 2, 2, 2, 2, 11 0 ? ? ?
178 2, 89 0 16 1 17
180 2, 2, 3, 3, 5 0 ? ? ?
182 2, 7, 13 4 23 2 25
184 2, 2, 2, 23 0 ? ? 31
186 2, 3, 31 1 26 0 26
188 2, 2, 47 0 25 0 25
190 2, 5, 19 0 23 0 23
192 2, 2, 2, 2, 2, 2, 3 3 ? ? ?
194 2, 97 1 18 1 19
196 2, 2, 7, 7 0 ? ? 35
198 2, 3, 3, 11 0 ? ? ?
200 2, 2, 2, 5, 5 1 ? ? 61
202 2, 101 0 18 1 19
204 2, 2, 3, 17 1 ? ? 53
206 2, 103 1 19 0 19
208 2, 2, 2, 2, 13 1 ? ? ?
210 2, 3, 5, 7 0 43 ? ?
212 2, 2, 53 0 29 ? 30
214 2, 107 0 19 0 19
216 2, 2, 2, 3, 3, 3 3 ? ? ?
218 2, 109 1 20 1 21
220 2, 2, 5, 11 3 ? ? ?
222 2, 3, 37 1 30 0 30
224 2, 2, 2, 2, 2, 7 3 ? ? ?
226 2, 113 0 20 1 21
228 2, 2, 3, 19 0 ? ? 57
230 2, 5, 23 0 27 0 27
232 2, 2, 2, 29 0 ? ? 40
234 2, 3, 3, 13 2 ? ? ?
236 2, 2, 59 0 31 0 31
238 2, 7, 17 0 27 ? ?
240 2, 2, 2, 2, 3, 5 3 ? ? ?
242 2, 11, 11 1 25 0 25
244 2, 2, 61 0 33 1 34
246 2, 3, 41 0 31 0 31
248 2, 2, 2, 31 1 ? ? 41
250 2, 5, 5, 5 1 ? ? 37
252 2, 2, 3, 3, 7 0 ? ? ?
254 2, 127 1 23 0 23
256 2, 2, 2, 2, 2, 2, 2, 2 4 ? ? 284
258 2, 3, 43 1 34 0 34