686:
637:
395:
622:
314:
702:
652:
375:
384:
667:
47:
300:
There are 28 six-vertex cycles in the
Heawood graph. Each 6-cycle is disjoint from exactly three other 6-cycles; among these three 6-cycles, each one is the symmetric difference of the other two. The graph with one node per 6-cycle, and one edge for each disjoint pair of 6-cycles, is the
293:. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is,
484:: it can be embedded in the plane such that adjacent vertices are exactly at distance one apart, with no two vertices embedded to the same point and no vertex embedded into a point within an edge.
608:
430:, the graph representing incidences between points and lines in that geometry. With this interpretation, the 6-cycles in the Heawood graph correspond to
297:) in eight different ways. Every two perfect matchings, and every two Hamiltonian cycles, can be transformed into each other by a symmetry of the graph.
1012:
776:
464:
685:
504:(7), a group of order 336. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Heawood graph is a
1082:
774:
Abreu, M.; Aldred, R. E. L.; Funk, M.; Jackson, Bill; Labbate, D.; Sheehan, J. (2004), "Graphs and digraphs with all 2-factors isomorphic",
222:
471:
508:. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. More strongly, the Heawood graph is
1096:
865:
692:
1152:
898:
861:
627:
454:
262:, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-
675:
636:
1170:
and Dobcsányi, P. "Trivalent
Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
666:
621:
1199:
348:
334:
531:
271:
197:
355:
in 1890, who proved that no map on the torus could require more than seven colors and thus this map is maximal.
701:
978:
651:
537:
1204:
497:
120:
94:
84:
610:. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
279:
201:
764:
Additions and
Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989)
64:
1056:
906:
267:
104:
707:
481:
359:
263:
193:
74:
1046:
955:
923:
840:
822:
493:
352:
247:
114:
57:
1102:
1088:
467:). Including the Heawood graph, there are 8 distinct graphs of order 14 with crossing number 3.
1092:
1074:
729:
394:
290:
209:
1021:
915:
880:
832:
785:
657:
516:, the Heawood graph, referenced as F014A, is the only cubic symmetric graph on 14 vertices.
286:
243:
132:
799:
1156:
1124:
795:
756:
642:
509:
505:
412:
326:
313:
213:
185:
162:
152:
142:
1149:
1060:
1167:
1078:
520:
322:
205:
28:
289:
in the
Heawood graph; for each matching, the set of edges not in the matching forms a
1193:
759:
513:
435:
302:
294:
275:
884:
524:
235:
172:
931:
844:
732:
374:
317:
Heawood's map. Opposite edges of the large hexagon are connected to form a torus.
383:
363:
259:
231:
189:
1026:
1004:
790:
427:
423:
407:
403:
347:
faces. Each face of the map is adjacent to every other face, thus as a result
737:
46:
17:
431:
927:
457:
3, and is the smallest cubic graph with that crossing number (sequence
439:
344:
836:
813:
Dejter, Italo J. (2011), "From the
Coxeter graph to the Klein graph",
919:
1051:
827:
330:
312:
351:
the map requires 7 colors. The map and graph were discovered by
1125:"Classification of Trivalent Symmetric Graphs of Small Order"
459:
540:
1043:
Eleven unit distance embeddings of the
Heawood graph
470:The Heawood graph is the smallest cubic graph with
181:
171:
161:
151:
141:
131:
113:
103:
93:
83:
73:
63:
53:
39:
602:
434:in the Fano plane. Also, the Heawood graph is the
31:, a graph family that contains the Heawood graph.
1183:. Master Thesis, University of Tübingen, 2018
1150:"Cubic Symmetric Graphs (The Foster Census)."
873:Bulletin of the American Mathematical Society
866:"Self-dual configurations and regular graphs"
8:
1005:"Graphs and obstructions in four dimensions"
366:such that every pair of faces is adjacent.
362:, the only known polyhedron apart from the
246:with 14 vertices and 21 edges, named after
1123:Conder, Marston; Morton, Margaret (1995).
496:of the Heawood graph is isomorphic to the
358:The map can be faithfully realized as the
1050:
1025:
1013:Journal of Combinatorial Theory, Series B
856:
854:
826:
789:
777:Journal of Combinatorial Theory, Series B
751:
749:
594:
578:
539:
720:
617:
603:{\displaystyle (x-3)(x+3)(x^{2}-2)^{6}}
36:
1132:Australasian Journal of Combinatorics
7:
309:Geometric and topological properties
1181:Engineering Linear Layouts with SAT
1087:. New York: North Holland. p.
1041:Gerbracht, Eberhard H.-A. (2009),
25:
472:Colin de Verdière graph invariant
34:Undirected graph with 14 vertices
960:Quarterly Journal of Mathematics
700:
684:
665:
650:
635:
620:
393:
382:
373:
45:
885:10.1090/S0002-9904-1950-09407-5
406:and two representations of its
1084:Graph Theory with Applications
958:(1890). "Map-colour theorem".
591:
571:
568:
556:
553:
541:
266:, the smallest cubic graph of
223:Table of graphs and parameters
1:
691:embedded in a torus (compare
27:Not to be confused with the
1003:Hein van der Holst (2006).
899:"The many names of (7,3,1)"
1221:
1027:10.1016/j.jctb.2005.09.004
791:10.1016/j.jctb.2004.09.004
26:
532:characteristic polynomial
422:The Heawood graph is the
329:without crossings onto a
272:distance-transitive graph
221:
44:
977:Szilassi, Lajos (1986),
534:of the Heawood graph is
254:Combinatorial properties
815:Journal of Graph Theory
498:projective linear group
480:The Heawood graph is a
321:The Heawood graph is a
604:
453:The Heawood graph has
318:
605:
325:; that is, it can be
316:
907:Mathematics Magazine
897:Brown, Ezra (2002).
672:embedded in a torus
538:
488:Algebraic properties
333:. The result is the
1061:2009arXiv0912.5395G
986:Structural Topology
757:Brouwer, Andries E.
708:Szilassi polyhedron
512:. According to the
482:unit distance graph
360:Szilassi polyhedron
198:Distance-transitive
1155:2008-07-20 at the
730:Weisstein, Eric W.
600:
494:automorphism group
353:Percy John Heawood
319:
248:Percy John Heawood
58:Percy John Heawood
1200:Individual graphs
979:"Regular toroids"
837:10.1002/jgt.20597
679:
676:shown as a square
416:
295:3-color its edges
291:Hamiltonian cycle
287:perfect matchings
228:
227:
217:Orientably simple
16:(Redirected from
1212:
1184:
1177:
1171:
1165:
1159:
1146:
1140:
1139:
1129:
1120:
1114:
1113:
1111:
1110:
1101:. Archived from
1071:
1065:
1063:
1054:
1038:
1032:
1031:
1029:
1009:
1000:
994:
993:
983:
974:
968:
967:
962:. First Series.
952:
946:
945:
943:
942:
936:
930:. Archived from
903:
894:
888:
887:
870:
858:
849:
847:
830:
810:
804:
802:
793:
771:
765:
763:
753:
744:
743:
742:
725:
704:
688:
673:
669:
658:chromatic number
654:
639:
624:
609:
607:
606:
601:
599:
598:
583:
582:
510:4-arc-transitive
476:
462:
410:
397:
386:
377:
342:
280:distance regular
278:) and therefore
244:undirected graph
202:Distance-regular
133:Chromatic number
49:
37:
21:
1220:
1219:
1215:
1214:
1213:
1211:
1210:
1209:
1190:
1189:
1188:
1187:
1178:
1174:
1166:
1162:
1157:Wayback Machine
1147:
1143:
1127:
1122:
1121:
1117:
1108:
1106:
1099:
1079:Murty, U. S. R.
1073:
1072:
1068:
1040:
1039:
1035:
1007:
1002:
1001:
997:
981:
976:
975:
971:
954:
953:
949:
940:
938:
934:
920:10.2307/3219140
901:
896:
895:
891:
868:
860:
859:
852:
812:
811:
807:
773:
772:
768:
760:"Heawood graph"
755:
754:
747:
733:"Heawood Graph"
728:
727:
726:
722:
717:
710:
705:
696:
689:
680:
670:
661:
655:
646:
643:chromatic index
640:
631:
628:crossing number
625:
616:
590:
574:
536:
535:
506:symmetric graph
503:
490:
474:
458:
455:crossing number
447:
443:
420:
419:
418:
417:
413:bipartite graph
400:
399:
398:
389:
388:
387:
379:
378:
341:
337:
311:
256:
216:
212:
208:
204:
200:
196:
192:
188:
143:Chromatic index
124:
35:
32:
23:
22:
15:
12:
11:
5:
1218:
1216:
1208:
1207:
1205:Regular graphs
1202:
1192:
1191:
1186:
1185:
1179:Jessica Wolz,
1172:
1160:
1141:
1115:
1097:
1066:
1033:
1020:(3): 388–404.
995:
969:
956:Heawood, P. J.
947:
889:
850:
805:
784:(2): 395–404,
766:
745:
719:
718:
716:
713:
712:
711:
706:
699:
697:
690:
683:
681:
671:
664:
662:
656:
649:
647:
641:
634:
632:
626:
619:
615:
612:
597:
593:
589:
586:
581:
577:
573:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
521:book thickness
501:
489:
486:
445:
441:
402:
401:
392:
391:
390:
381:
380:
372:
371:
370:
369:
368:
339:
323:toroidal graph
310:
307:
255:
252:
226:
225:
219:
218:
183:
179:
178:
175:
169:
168:
165:
163:Book thickness
159:
158:
155:
149:
148:
145:
139:
138:
135:
129:
128:
122:
117:
111:
110:
107:
101:
100:
97:
91:
90:
87:
81:
80:
77:
71:
70:
67:
61:
60:
55:
51:
50:
42:
41:
33:
29:Heawood graphs
24:
14:
13:
10:
9:
6:
4:
3:
2:
1217:
1206:
1203:
1201:
1198:
1197:
1195:
1182:
1176:
1173:
1169:
1164:
1161:
1158:
1154:
1151:
1145:
1142:
1137:
1133:
1126:
1119:
1116:
1105:on 2010-04-13
1104:
1100:
1098:0-444-19451-7
1094:
1090:
1086:
1085:
1080:
1076:
1070:
1067:
1062:
1058:
1053:
1048:
1044:
1037:
1034:
1028:
1023:
1019:
1015:
1014:
1006:
999:
996:
991:
987:
980:
973:
970:
965:
961:
957:
951:
948:
937:on 2012-02-05
933:
929:
925:
921:
917:
913:
909:
908:
900:
893:
890:
886:
882:
878:
874:
867:
863:
857:
855:
851:
846:
842:
838:
834:
829:
824:
820:
816:
809:
806:
801:
797:
792:
787:
783:
779:
778:
770:
767:
761:
758:
752:
750:
746:
740:
739:
734:
731:
724:
721:
714:
709:
703:
698:
694:
687:
682:
677:
668:
663:
659:
653:
648:
644:
638:
633:
629:
623:
618:
613:
611:
595:
587:
584:
579:
575:
565:
562:
559:
550:
547:
544:
533:
528:
526:
522:
517:
515:
514:Foster census
511:
507:
499:
495:
487:
485:
483:
478:
473:
468:
466:
461:
456:
451:
449:
438:of the group
437:
436:Tits building
433:
429:
425:
414:
409:
405:
396:
385:
376:
367:
365:
361:
356:
354:
350:
346:
336:
332:
328:
324:
315:
308:
306:
304:
303:Coxeter graph
298:
296:
292:
288:
285:There are 24
283:
281:
277:
276:Foster census
273:
269:
265:
261:
258:The graph is
253:
251:
249:
245:
241:
240:Heawood graph
237:
233:
224:
220:
215:
211:
207:
203:
199:
195:
191:
187:
184:
180:
176:
174:
170:
166:
164:
160:
156:
154:
150:
146:
144:
140:
136:
134:
130:
126:
118:
116:
115:Automorphisms
112:
108:
106:
102:
98:
96:
92:
88:
86:
82:
78:
76:
72:
68:
66:
62:
59:
56:
52:
48:
43:
40:Heawood graph
38:
30:
19:
1180:
1175:
1163:
1144:
1135:
1131:
1118:
1107:. Retrieved
1103:the original
1083:
1075:Bondy, J. A.
1069:
1042:
1036:
1017:
1011:
998:
989:
985:
972:
963:
959:
950:
939:. Retrieved
932:the original
914:(2): 83–94.
911:
905:
892:
876:
872:
818:
814:
808:
781:
775:
769:
736:
723:
529:
525:queue number
518:
491:
479:
469:
452:
421:
411:(below as a
357:
320:
299:
284:
257:
239:
236:graph theory
232:mathematical
229:
173:Queue number
364:tetrahedron
335:regular map
270:6. It is a
210:Hamiltonian
54:Named after
18:Heawood map
1194:Categories
1168:Conder, M.
1148:Royle, G.
1109:2019-12-18
966:: 322–339.
941:2006-10-27
715:References
428:Fano plane
424:Levi graph
408:Levi graph
404:Fano plane
182:Properties
1052:0912.5395
828:1002.1960
738:MathWorld
585:−
548:−
432:triangles
345:hexagonal
343:, with 7
274:(see the
234:field of
214:Symmetric
186:Bipartite
1153:Archived
1081:(1976).
864:(1950),
349:coloring
327:embedded
206:Toroidal
95:Diameter
65:Vertices
1057:Bibcode
992:: 69–80
928:3219140
862:Coxeter
821:: 1–9,
800:2099150
614:Gallery
519:It has
463:in the
460:A110507
426:of the
230:In the
1138:: 146.
1095:
926:
845:754481
843:
798:
523:3 and
242:is an
238:, the
85:Radius
1128:(PDF)
1047:arXiv
1008:(PDF)
982:(PDF)
935:(PDF)
924:JSTOR
902:(PDF)
869:(PDF)
841:S2CID
823:arXiv
693:video
475:μ = 6
338:{6,3}
331:torus
268:girth
260:cubic
190:Cubic
153:Genus
119:336 (
105:Girth
75:Edges
1093:ISBN
530:The
492:The
465:OEIS
264:cage
194:Cage
1089:237
1022:doi
916:doi
881:doi
833:doi
786:doi
527:2.
500:PGL
340:2,1
125:(7)
121:PGL
1196::
1136:11
1134:.
1130:.
1091:.
1077:;
1055:,
1045:,
1018:96
1016:.
1010:.
990:13
988:,
984:,
964:24
922:.
912:75
910:.
904:.
879:,
877:56
875:,
871:,
853:^
839:,
831:,
819:70
817:,
796:MR
794:,
782:92
780:,
748:^
735:.
477:.
450:.
444:(F
440:SL
305:.
282:.
250:.
79:21
69:14
1112:.
1064:.
1059::
1049::
1030:.
1024::
944:.
918::
883::
848:.
835::
825::
803:.
788::
762:.
741:.
695:)
678:)
674:(
660:2
645:3
630:3
596:6
592:)
588:2
580:2
576:x
572:(
569:)
566:3
563:+
560:x
557:(
554:)
551:3
545:x
542:(
502:2
448:)
446:2
442:3
415:)
177:2
167:3
157:1
147:3
137:2
127:)
123:2
109:6
99:3
89:3
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
