382:
366:
398:
418:
41:
20:
214:
rather than on the Möbius strip. If one cuts a hole from this subdivision of the projective plane, surrounding a single vertex, the surrounded vertex is replaced by a triangle of region boundaries around the hole, giving the previously described construction of the Tietze graph.
272:
that is not 3-edge-colorable. However, most authors restrict snarks to graphs without 3-cycles, so Tietze's graph is not generally considered to be a snark. Nevertheless, it is
198:. The boundary segments of the regions of Tietze's subdivision (including the segments along the boundary of the Möbius strip itself) form an embedding of Tietze's graph.
190:
can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are
210:
by replacing one of its vertices with a triangle. Like the Tietze graph, the
Petersen graph forms the boundary of six mutually touching regions, but on the
381:
397:
257:
Tietze's graph requires four colors; that is, its chromatic index is 4. Equivalently, the edges of Tietze's graph can be partitioned into four
365:
350:(including both rotations and reflections). This group has two orbits of size 3 and one of size 6 on vertices, and thus this graph is not
152:
417:
27:
into six mutually-adjacent regions. The vertices and edges of the subdivision form an embedding of Tietze's graph onto the strip.
458:
183:
611:
Esperet, L.; Mazzuoccolo, G. (2014), "On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings",
404:
285:
179:
462:
669:
236:
674:
351:
316:
258:
81:
71:
243:
51:
328:
312:
265:
145:
91:
576:
Isaacs, R. (1975), "Infinite families of nontrivial trivalent graphs which are not Tait colorable",
320:
61:
246:: removing one of its three triangle vertices forms a smaller graph that remains non-Hamiltonian.
646:
620:
593:
508:
324:
296:
101:
526:
332:
273:
228:
630:
585:
500:
372:
292:
269:
232:
211:
173:
118:
642:
638:
388:
344:
191:
128:
187:
24:
551:
438:
434:
408:
336:
207:
195:
107:
663:
512:
254:
650:
281:
165:
529:
300:
176:
161:
141:
40:
491:
Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs",
534:
465:[Some remarks on the problem of map coloring on one-sided surfaces]
19:
463:"Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen"
299:
that testing whether a graph can be covered by four perfect matchings is
597:
504:
347:
634:
589:
291:
Unlike the
Petersen graph, the Tietze graph can be covered by four
625:
550:
Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007),
559:
International
Journal of Computer Science and Network Security
311:
Tietze's graph has chromatic number 3, chromatic index 4,
231:, but any two non-adjacent vertices can be connected by a
239:
cubic non-Hamiltonian graphs with 12 or fewer vertices.
235:. Tietze's graph and the Petersen graph are the only
16:
Undirected cubic graph with 12 vertices and 18 edges
584:(3), Mathematical Association of America: 221–239,
264:Tietze's graph matches part of the definition of a
137:
127:
117:
100:
90:
80:
70:
60:
50:
33:
423:A three-dimensional embedding of the Tietze graph.
242:Unlike the Petersen graph, Tietze's graph is not
182:with 12 vertices and 18 edges. It is named after
223:Both Tietze's graph and the Petersen graph are
8:
624:
18:
450:
361:
295:. This property plays a key role in a
206:Tietze's graph may be formed from the
194:onto the Möbius strip may require six
30:
7:
486:
484:
250:Edge coloring and perfect matchings
441:, two other 12-vertex cubic graphs
14:
552:"Almost Hamiltonian cubic graphs"
416:
396:
380:
364:
280:, part of an infinite family of
39:
493:Periodica Mathematica Hungarica
343:, the group of symmetries of a
184:Heinrich Franz Friedrich Tietze
186:, who showed in 1910 that the
153:Table of graphs and parameters
1:
691:
202:Relation to Petersen graph
23:Tietze's subdivision of a
391:of the Tietze graph is 4.
375:of the Tietze graph is 3.
151:
38:
225:maximally nonhamiltonian
613:Journal of Graph Theory
28:
403:The Tietze graph has
307:Additional properties
22:
578:Amer. Math. Monthly
321:independence number
527:Weisstein, Eric W.
505:10.1007/BF02023582
325:automorphism group
237:2-vertex-connected
29:
670:Individual graphs
635:10.1002/jgt.21778
471:DMV Annual Report
352:vertex-transitive
293:perfect matchings
229:Hamiltonian cycle
158:
157:
682:
655:
653:
628:
608:
602:
600:
573:
567:
566:
556:
547:
541:
540:
539:
530:"Tietze's Graph"
522:
516:
515:
488:
479:
478:
468:
459:Tietze, Heinrich
455:
420:
400:
384:
373:chromatic number
368:
270:bridgeless graph
268:: it is a cubic
261:, but no fewer.
233:Hamiltonian path
212:projective plane
119:Chromatic number
45:The Tietze graph
43:
31:
690:
689:
685:
684:
683:
681:
680:
679:
660:
659:
658:
610:
609:
605:
590:10.2307/2319844
575:
574:
570:
554:
549:
548:
544:
525:
524:
523:
519:
490:
489:
482:
466:
457:
456:
452:
448:
431:
424:
421:
412:
405:crossing number
401:
392:
389:chromatic index
385:
376:
369:
360:
342:
309:
279:
252:
244:hypohamiltonian
227:: they have no
221:
204:
144:
129:Chromatic index
111:
46:
17:
12:
11:
5:
688:
686:
678:
677:
675:Regular graphs
672:
662:
661:
657:
656:
619:(2): 144–157,
603:
568:
542:
517:
480:
449:
447:
444:
443:
442:
439:Franklin graph
430:
427:
426:
425:
422:
415:
413:
402:
395:
393:
386:
379:
377:
370:
363:
359:
356:
340:
337:dihedral group
308:
305:
284:introduced by
277:
276:to the graph J
251:
248:
220:
217:
208:Petersen graph
203:
200:
170:Tietze's graph
156:
155:
149:
148:
139:
135:
134:
131:
125:
124:
121:
115:
114:
109:
104:
98:
97:
94:
88:
87:
84:
78:
77:
74:
68:
67:
64:
58:
57:
54:
48:
47:
44:
36:
35:
34:Tietze's graph
15:
13:
10:
9:
6:
4:
3:
2:
687:
676:
673:
671:
668:
667:
665:
652:
648:
644:
640:
636:
632:
627:
622:
618:
614:
607:
604:
599:
595:
591:
587:
583:
579:
572:
569:
564:
560:
553:
546:
543:
537:
536:
531:
528:
521:
518:
514:
510:
506:
502:
498:
494:
487:
485:
481:
476:
472:
464:
460:
454:
451:
445:
440:
436:
433:
432:
428:
419:
414:
410:
406:
399:
394:
390:
383:
378:
374:
367:
362:
357:
355:
353:
349:
346:
338:
334:
330:
326:
322:
318:
314:
306:
304:
302:
298:
294:
289:
287:
283:
282:flower snarks
275:
271:
267:
262:
260:
256:
255:Edge coloring
249:
247:
245:
240:
238:
234:
230:
226:
219:Hamiltonicity
218:
216:
213:
209:
201:
199:
197:
193:
189:
185:
181:
178:
175:
171:
167:
163:
154:
150:
147:
143:
140:
136:
132:
130:
126:
122:
120:
116:
112:
105:
103:
102:Automorphisms
99:
95:
93:
89:
85:
83:
79:
75:
73:
69:
65:
63:
59:
55:
53:
49:
42:
37:
32:
26:
21:
616:
612:
606:
581:
577:
571:
562:
558:
545:
533:
520:
499:(1): 57–68,
496:
492:
474:
470:
453:
310:
290:
263:
253:
241:
224:
222:
205:
188:Möbius strip
169:
166:graph theory
162:mathematical
159:
25:Möbius strip
435:DĂĽrer graph
331:12, and is
301:NP-complete
664:Categories
565:(1): 83–86
333:isomorphic
323:is 5. Its
274:isomorphic
174:undirected
138:Properties
626:1301.6926
535:MathWorld
513:122218690
477:: 155–159
407:2 and is
288:in 1975.
286:R. Isaacs
259:matchings
164:field of
651:15284123
461:(1910),
429:See also
409:1-planar
319:3. The
317:diameter
192:embedded
82:Diameter
52:Vertices
643:3246172
598:2319844
358:Gallery
348:hexagon
345:regular
335:to the
160:In the
649:
641:
596:
511:
315:3 and
196:colors
172:is an
72:Radius
647:S2CID
621:arXiv
594:JSTOR
555:(PDF)
509:S2CID
467:(PDF)
446:Notes
329:order
313:girth
297:proof
266:snark
180:graph
177:cubic
146:Snark
142:Cubic
92:Girth
62:Edges
437:and
387:The
371:The
327:has
106:12 (
631:doi
586:doi
501:doi
666::
645:,
639:MR
637:,
629:,
617:77
615:,
592:,
582:82
580:,
561:,
557:,
532:.
507:,
497:14
495:,
483:^
475:19
473:,
469:,
354:.
303:.
168:,
66:18
56:12
654:.
633::
623::
601:.
588::
563:7
538:.
503::
411:.
341:6
339:D
278:3
133:4
123:3
113:)
110:6
108:D
96:3
86:3
76:3
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
