Peripheral cycle

---

title: "Peripheral cycle" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-theory-objects", "planar-graphs"] description: "Graph cycle which does not separate remaining elements" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Peripheral_cycle" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Graph cycle which does not separate remaining elements ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/8/86/6n-graf-clique.svg" caption="In this graph, the red triangle formed by vertices 1, 2, and 5 is a peripheral cycle: the four remaining edges form a single bridge. However, pentagon 1–2–3–4–5 is not peripheral, as the two remaining edges form two separate bridges."] ::

In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.{{citation | last = Tutte | first = W. T. | author-link = W. T. Tutte | journal = Proceedings of the London Mathematical Society | mr = 0158387 | pages = 743–767 | series = Third Series | title = How to draw a graph | volume = 13 | year = 1963 | doi=10.1112/plms/s3-13.1.743}}.

Definitions

A peripheral cycle C in a graph G can be defined formally in one of several equivalent ways:

• C is peripheral if it is a simple cycle in a connected graph with the property that, for every two edges e_1 and e_2 in G\setminus C, there exists a path in G that starts with e_1, ends with e_2, and has no interior vertices belonging to C.{{citation | last1 = Di Battista | first1 = Giuseppe | last2 = Eades | first2 = Peter | author2-link = Peter Eades | last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia | last4 = Tollis | first4 = Ioannis G. | isbn = 978-0-13-301615-4 | pages = 74–75 | publisher = Prentice Hall | title = Graph Drawing: Algorithms for the Visualization of Graphs | year = 1998}}.
• If C is any subgraph of G, a bridge of C is a minimal subgraph B of G that is edge-disjoint from C and that has the property that all of its points of attachment (vertices adjacent to edges in both B and G\setminus B) belong to C.{{citation | last = Tutte | first = W. T. | author-link = W. T. Tutte | journal = Proceedings of the London Mathematical Society | mr = 0114774 | pages = 304–320 | series = Third Series | title = Convex representations of graphs | volume = 10 | year = 1960 | doi = 10.1112/plms/s3-10.1.304}}. A simple cycle C is peripheral if it has exactly one bridge.
• In a connected graph that is not a theta graph, peripheral cycles cannot have chords, because any chord would be a bridge, separated from the rest of the graph. In this case, C is peripheral if it is an induced cycle with the property that the subgraph G\setminus C formed by deleting the edges and vertices of C is connected.

The equivalence of these definitions is not hard to see: a connected subgraph of G\setminus C (together with the edges linking it to C), or a chord of a cycle that causes it to fail to be induced, must in either case be a bridge, and must also be an equivalence class of the binary relation on edges in which two edges are related if they are the ends of a path with no interior vertices in C.

Properties

Peripheral cycles appear in the theory of polyhedral graphs, that is, 3-vertex-connected planar graphs. For every planar graph G, and every planar embedding of G, the faces of the embedding that are induced cycles must be peripheral cycles. In a polyhedral graph, all faces are peripheral cycles, and every peripheral cycle is a face. It follows from this fact that (up to combinatorial equivalence, the choice of the outer face, and the orientation of the plane) every polyhedral graph has a unique planar embedding.See the remarks following Theorem 2.8 in . As Tutte observes, this was already known to Hassler Whitney: {{citation | last = Whitney | first = Hassler | doi = 10.2307/1989545 | issue = 2 | journal = Transactions of the American Mathematical Society | mr = 1501641 | pages = 339–362 | title = Non-separable and planar graphs | volume = 34 | year = 1932 | jstor = 1989545 | doi-access = free

In planar graphs, the cycle space is generated by the faces, but in non-planar graphs peripheral cycles play a similar role: for every 3-vertex-connected finite graph, the cycle space is generated by the peripheral cycles. The result can also be extended to locally finite but infinite graphs.{{citation | last = Bruhn | first = Henning | doi = 10.1016/j.jctb.2004.03.005 | issue = 2 | journal = Journal of Combinatorial Theory | mr = 2099143 | pages = 235–256 | series = Series B | title = The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits | volume = 92 | year = 2004| doi-access = free | last1 = Thomassen | first1 = Carsten | author1-link = Carsten Thomassen (mathematician) | last2 = Toft | first2 = Bjarne | doi = 10.1016/S0095-8956(81)80025-1 | issue = 2 | journal = Journal of Combinatorial Theory | mr = 630983 | pages = 199–224 | series = Series B | title = Non-separating induced cycles in graphs | volume = 31 | year = 1981| doi-access = free

Peripheral cycles in 3-connected graphs can be computed in linear time and have been used for designing planarity tests.{{citation | last1 = Schmidt | first1 = Jens M. | doi = 10.1007/978-3-662-43948-7_80 | title = Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14) | pages = 967–978 | contribution = The Mondshein Sequence | year = 2014 | series=Lecture Notes in Computer Science| volume = 8572 | isbn = 978-3-662-43947-0 They were also extended to the more general notion of non-separating ear decompositions. In some algorithms for testing planarity of graphs, it is useful to find a cycle that is not peripheral, in order to partition the problem into smaller subproblems. In a biconnected graph of circuit rank less than three (such as a cycle graph or theta graph) every cycle is peripheral, but every biconnected graph with circuit rank three or more has a non-peripheral cycle, which may be found in linear time.

Generalizing chordal graphs, define a strangulated graph to be a graph in which every peripheral cycle is a triangle. They characterize these graphs as being the clique-sums of chordal graphs and maximal planar graphs.{{citation | last1 = Seymour | first1 = P. D. | author1-link = Paul Seymour (mathematician) | last2 = Weaver | first2 = R. W. | doi = 10.1002/jgt.3190080206 | issue = 2 | journal = Journal of Graph Theory | mr = 742878 | pages = 241–251 | title = A generalization of chordal graphs | volume = 8 | year = 1984}}.

Related concepts

Peripheral cycles have also been called non-separating cycles, but this term is ambiguous, as it has also been used for two related but distinct concepts: simple cycles the removal of which would disconnect the remaining graph,E.g. see {{citation | last1 = Borse | first1 = Y. M. | last2 = Waphare | first2 = B. N. | issue = 1–4 | journal = The Journal of the Indian Mathematical Society | mr = 2662989 | pages = 75–92 (2009) | series = New Series | title = Vertex disjoint non-separating cycles in graphs | volume = 75 | year = 2008}}. and cycles of a topologically embedded graph such that cutting along the cycle would not disconnect the surface on which the graph is embedded.E.g. see {{citation | last1 = Cabello | first1 = Sergio | last2 = Mohar | first2 = Bojan | doi = 10.1007/s00454-006-1292-5 | issue = 2 | journal = Discrete and Computational Geometry | mr = 2295054 | pages = 213–235 | title = Finding shortest non-separating and non-contractible cycles for topologically embedded graphs | volume = 37 | year = 2007| doi-access = free

In matroids, a non-separating circuit is a circuit of the matroid (that is, a minimal dependent set) such that deleting the circuit leaves a smaller matroid that is connected (that is, that cannot be written as a direct sum of matroids).{{citation | last1 = Maia | first1 = Bráulio, Junior | last2 = Lemos | first2 = Manoel | last3 = Melo | first3 = Tereza R. B. | contribution = Non-separating circuits and cocircuits in matroids | doi = 10.1093/acprof:oso/9780198571278.003.0010 | location = Oxford | mr = 2314567 | pages = 162–171 | publisher = Oxford Univ. Press | series = Oxford Lecture Ser. Math. Appl. | title = Combinatorics, complexity, and chance | volume = 34 | year = 2007| isbn = 978-0-19-857127-8

References

References

1. Not to be confused with [[bridge (graph theory)]], a different concept.
2. This is the definition of peripheral cycles originally used by {{harvtxt. Tutte. 1963. {{harvtxt. Seymour. Weaver. 1984 use the same definition of a peripheral cycle, but with a different definition of a bridge that more closely resembles the induced-cycle definition for peripheral cycles.
3. This is, essentially, the definition used by {{harvtxt. Bruhn. 2004. However, Bruhn distinguishes the case that G has isolated vertices from disconnections caused by the removal of C.
4. See e.g. Theorem 2.4 of {{harvtxt. Tutte. 1960, showing that the vertex sets of bridges are path-connected, see {{harvtxt. Seymour. Weaver. 1984 for a definition of bridges using chords and connected components, and also see {{harvtxt. Di Battista. Eades. Tamassia. Tollis. 1998 for a definition of bridges using equivalence classes of the binary relation on edges.
5. {{harvtxt. Tutte. 1963, Theorems 2.7 and 2.8.
6. {{harvtxt. Tutte. 1963, Theorem 2.5.
7. {{harvtxt. Di Battista. Eades. Tamassia. Tollis. 1998, Lemma 3.4, pp. 75–76.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::