In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip 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 embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision form an embedding of Tietze's graph.

Heinrich Franz Friedrich Tietze was an Austrian mathematician, famous for the Tietze extension theorem on functions from topological spaces to the real numbers. He also developed the Tietze transformations for group presentations, and was the first to pose the group isomorphism problem. Tietze's graph is also named after him; it describes the boundaries of a subdivision of the Möbius strip into six mutually-adjacent regions, found by Tietze as part of an extension of the four color theorem to non-orientable surfaces.