472:
504:
520:
488:
29:
536:
214:
The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the
449:
455:
The automorphism group of the McGee graph is of order 32 and doesn't act transitively upon its vertices: there are two vertex orbits, of lengths 8 and 16. The McGee graph is the smallest cubic cage that is not a
211:
First discovered by Sachs but unpublished, the graph is named after McGee who published the result in 1960. Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966.
471:
274:
697:
519:
503:
165:
487:
611:
478:
595:
Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960
535:
795:
216:
265:
677:
Brouwer, A. E.; Cohen, A. M.; and
Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
241:
800:
651:
457:
77:
67:
716:
245:
47:
87:
154:
57:
762:
Jajcay, Robert; Širáň, Jozef (2011). "Small vertex-transitive graphs of given degree and girth".
692:"Sequence A110507 (Number of nodes in the smallest cubic graph with crossing number n)"
97:
572:
158:
771:
728:
660:
620:
526:
494:
233:
107:
510:
237:
127:
117:
639:
Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of
Toronto Press, 1966
28:
249:
789:
190:
712:
253:
178:
137:
444:{\displaystyle x^{3}(x-3)(x-2)^{3}(x+1)^{2}(x+2)(x^{2}+x-4)(x^{3}+x^{2}-4x-2)^{4}}
687:
575:
226:
205:
201:
174:
150:
775:
197:
580:
664:
625:
606:
733:
204:
of girth 7). It is also the smallest cubic cage that is not a
691:
277:
146:
136:
126:
116:
106:
96:
86:
76:
66:
56:
46:
38:
21:
443:
752:. Master Thesis, University of Tübingen, 2018
8:
566:
564:
562:
560:
558:
556:
232:The McGee graph has radius 4, diameter 4,
732:
698:On-Line Encyclopedia of Integer Sequences
624:
435:
410:
397:
369:
341:
319:
282:
276:
649:Wong, Pak-Ken (1982). "Cages—A Survey".
552:
541:Alternative drawing of the McGee graph.
467:
607:"A Minimal Cubic Graph of Girth Seven"
18:
7:
196:The McGee graph is the unique (3,7)-
750:Engineering Linear Layouts with SAT
16:Graph with 24 vertices and 36 edges
14:
534:
518:
502:
486:
470:
27:
193:with 24 vertices and 36 edges.
612:Canadian Mathematical Bulletin
432:
390:
387:
362:
359:
347:
338:
325:
316:
303:
300:
288:
166:Table of graphs and parameters
1:
764:Ars Mathematica Contemporanea
529:of the McGee graph is 3.
513:of the McGee graph is 3.
497:of the McGee graph is 3.
481:of the McGee graph is 8.
817:
776:10.26493/1855-3974.124.06d
688:Sloane, N. J. A.
217:generalized Petersen graph
266:characteristic polynomial
164:
26:
717:"Crossing number graphs"
527:acyclic chromatic number
652:Journal of Graph Theory
458:vertex-transitive graph
268:of the McGee graph is
665:10.1002/jgt.3190060103
626:10.4153/CMB-1960-018-1
445:
605:McGee, W. F. (1960).
446:
275:
260:Algebraic properties
225:, also known as the
721:Mathematica Journal
715:; Exoo, G. (2009).
734:10.3888/tmj.11.2-2
701:. OEIS Foundation.
573:Weisstein, Eric W.
441:
240:3. It is also a 3-
796:Individual graphs
171:
170:
808:
780:
779:
759:
753:
746:
740:
738:
736:
709:
703:
702:
684:
678:
675:
669:
668:
646:
640:
637:
631:
630:
628:
602:
596:
593:
587:
586:
585:
568:
538:
522:
506:
495:chromatic number
490:
474:
450:
448:
447:
442:
440:
439:
415:
414:
402:
401:
374:
373:
346:
345:
324:
323:
287:
286:
242:vertex-connected
234:chromatic number
224:
108:Chromatic number
31:
19:
816:
815:
811:
810:
809:
807:
806:
805:
786:
785:
784:
783:
761:
760:
756:
747:
743:
711:
710:
706:
686:
685:
681:
676:
672:
648:
647:
643:
638:
634:
604:
603:
599:
594:
590:
571:
570:
569:
554:
549:
542:
539:
530:
523:
514:
511:chromatic index
507:
498:
491:
482:
479:crossing number
475:
466:
431:
406:
393:
365:
337:
315:
278:
273:
272:
262:
238:chromatic index
219:
157:
153:
118:Chromatic index
34:
33:The McGee graph
17:
12:
11:
5:
814:
812:
804:
803:
801:Regular graphs
798:
788:
787:
782:
781:
770:(2): 375–384.
754:
748:Jessica Wolz,
741:
704:
679:
670:
641:
632:
619:(2): 149–152.
597:
588:
551:
550:
548:
545:
544:
543:
540:
533:
531:
524:
517:
515:
508:
501:
499:
492:
485:
483:
476:
469:
465:
462:
453:
452:
438:
434:
430:
427:
424:
421:
418:
413:
409:
405:
400:
396:
392:
389:
386:
383:
380:
377:
372:
368:
364:
361:
358:
355:
352:
349:
344:
340:
336:
333:
330:
327:
322:
318:
314:
311:
308:
305:
302:
299:
296:
293:
290:
285:
281:
261:
258:
250:book thickness
248:graph. It has
246:edge-connected
200:(the smallest
169:
168:
162:
161:
148:
144:
143:
140:
134:
133:
130:
128:Book thickness
124:
123:
120:
114:
113:
110:
104:
103:
100:
94:
93:
90:
84:
83:
80:
74:
73:
70:
64:
63:
60:
54:
53:
50:
44:
43:
40:
36:
35:
32:
24:
23:
15:
13:
10:
9:
6:
4:
3:
2:
813:
802:
799:
797:
794:
793:
791:
777:
773:
769:
765:
758:
755:
751:
745:
742:
735:
730:
726:
722:
718:
714:
708:
705:
700:
699:
693:
689:
683:
680:
674:
671:
666:
662:
658:
654:
653:
645:
642:
636:
633:
627:
622:
618:
614:
613:
608:
601:
598:
592:
589:
583:
582:
577:
576:"McGee Graph"
574:
567:
565:
563:
561:
559:
557:
553:
546:
537:
532:
528:
521:
516:
512:
505:
500:
496:
489:
484:
480:
473:
468:
463:
461:
459:
436:
428:
425:
422:
419:
416:
411:
407:
403:
398:
394:
384:
381:
378:
375:
370:
366:
356:
353:
350:
342:
334:
331:
328:
320:
312:
309:
306:
297:
294:
291:
283:
279:
271:
270:
269:
267:
259:
257:
255:
251:
247:
243:
239:
235:
230:
228:
222:
218:
212:
209:
207:
203:
199:
194:
192:
191:regular graph
188:
184:
180:
176:
167:
163:
160:
156:
152:
149:
145:
141:
139:
135:
131:
129:
125:
121:
119:
115:
111:
109:
105:
101:
99:
98:Automorphisms
95:
91:
89:
85:
81:
79:
75:
71:
69:
65:
61:
59:
55:
51:
49:
45:
41:
37:
30:
25:
20:
767:
763:
757:
749:
744:
724:
720:
707:
695:
682:
673:
656:
650:
644:
635:
616:
610:
600:
591:
579:
454:
263:
254:queue number
231:
220:
213:
210:
195:
186:
182:
179:graph theory
175:mathematical
172:
138:Queue number
713:Pegg, E. T.
227:Nauru graph
206:Moore graph
202:cubic graph
183:McGee graph
159:Hamiltonian
42:W. F. McGee
39:Named after
22:McGee graph
790:Categories
547:References
187:(3-7)-cage
147:Properties
581:MathWorld
426:−
417:−
382:−
310:−
295:−
177:field of
659:: 1–22.
244:and a 3-
78:Diameter
48:Vertices
690:(ed.).
464:Gallery
189:is a 3-
185:or the
173:In the
252:3 and
236:3 and
223:(12,5)
181:, the
68:Radius
727:(2).
151:Cubic
88:Girth
58:Edges
696:The
525:The
509:The
493:The
477:The
264:The
198:cage
155:Cage
772:doi
729:doi
661:doi
621:doi
256:2.
792::
766:.
725:11
723:.
719:.
694:.
655:.
615:.
609:.
578:.
555:^
460:.
229:.
208:.
102:32
62:36
52:24
778:.
774::
768:4
739:.
737:.
731::
667:.
663::
657:6
629:.
623::
617:3
584:.
451:.
437:4
433:)
429:2
423:x
420:4
412:2
408:x
404:+
399:3
395:x
391:(
388:)
385:4
379:x
376:+
371:2
367:x
363:(
360:)
357:2
354:+
351:x
348:(
343:2
339:)
335:1
332:+
329:x
326:(
321:3
317:)
313:2
307:x
304:(
301:)
298:3
292:x
289:(
284:3
280:x
221:G
142:2
132:3
122:3
112:3
92:7
82:4
72:4
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
