Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Depends on

• A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
• Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree

Used by

• Every finite simple graph of minimum degree at least two contains a cycle Corollary
• Every tree with at least two vertices has at least two leaves Corollary
• Every triangle-free simple planar graph with n≥3 vertices has at most 2n-4 edges Corollary
• A split set in a bull-free graph Definition
• Alternating and augmenting paths relative to a matching Definition
• Arc-disjoint, edge-disjoint and internally vertex-disjoint path families and their local separators Definition
• Connected graphs and connected components defined by the existence of vertex paths Definition
• Directed and undirected Hamiltonian path and cycle decision problems Definition
• Directed walks, trails, paths and cycles, and strong connectivity Definition
• Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices Definition
• Euler trails and Euler circuits in multigraphs and digraphs Definition
• Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention Definition
• Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs Definition
• Holes, antiholes, and odd holes Definition
• Trees, forests, leaves and isolated vertices Definition
• Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set Definition
• A small graph separates walks, trails, paths, closed walks and cycles by explicit vertex lists Example
• The two induced co-E witnesses behind the forbidden path runs Example
• A vertex mixed on a connected set has opposite adjacency on some edge of that set Lemma
• Adding an edge between two nonadjacent vertices of a tree creates exactly one cycle Lemma
• An edge of a finite graph is a bridge if and only if it lies on no cycle Lemma
• Being joined by a walk or path is the same equivalence relation on the vertex set Lemma
• Deleting any edge of a tree separates it into exactly two tree components Lemma
• Every closed walk of odd length contains a cycle of odd length Lemma
• Every walk between two vertices contains a path between the same endpoints Lemma
• For five cyclically ordered neighbours of a plane vertex, alternating Kempe paths between the first and third and between the second and fourth cannot both occur Lemma
• If two distinct faces of a connected plane graph have the same boundary subgraph, then the graph is a cycle Lemma
• In a connected graph, some vertex outside a nonempty proper module is complete to it Lemma
• On a finite vertex set the graph notions agree, and on connected graphs the two path distances agree Lemma
• Relative to a complete nonedge pair in a co-E-free graph, a one-sided vertex mixed on an induced path avoids two consecutive nonneighbours and three consecutive neighbours Lemma
• Relative to a complete nonedge pair in a co-E-free graph, every one-sided vertex is pure to an induced H₅ Lemma
• The expected number of cycles of length at most ℓ in G(n,p) Lemma
• The symmetric difference of two matchings is a disjoint union of alternating paths and even cycles Lemma
• A two-connected plane graph of order at least three is maximal exactly when every face is triangular Proposition
• Every face of a two-connected plane graph is bounded by a cycle Proposition
• Directed Hamiltonian cycle polynomial-time many-one reduces to undirected Hamiltonian cycle Theorem
• Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity Theorem
• Every nonempty finite simple graph contains a path with at least δ(G) edges Theorem
• Every P₃-free graph G satisfies hom(G)≥√|V(G)| Theorem
• The (i,j) entry of A(G)ᵏ counts walks of length k Theorem

…and 1 more result.

Dependency tree · two levels

3 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

• University of Lethbridge, Combinatorics: A Guided Tour, Paths and Cycles (standard reference, not scraped)