Trails, Walks, Paths and Cycles

Basic Definitions §

Trails and Walks §

• Let be an undirected graph.

  A walk in is a finite sequence of vertices and edges of the form

  such that and and each edge is incident to the vertices to its left and right in the sequence (i.e., ).

  We do not require that each vertex and each edge is distinct from each other.

  • In the definition we call as the initial vertex and as the final vertex of the walk.
  • If the initial vertex is and the final vertex is , the walk is called a -path
  • The length of a walk refers to the number of edges in the walk.

• A trail is a walk in which all edges are distinct.

  • A -trail is a trail which starts and ends at and respectively.

Path §

• A path is a graph with the following property with the following property.

  We may list the vertices as such that the only edges are of the form for .

  • A path is a trail where we also require the vertices to be distinct from each other.

• We denote the path graph on vertices as . We call its length

• We say that a path is in a graph if

• If the path starts with vertex and ends with , such a path is called a -path

• A family of paths in a graph is edge independent or edge disjoint if no edge of is an edge of more than one path in the family

• A family of paths in a graph is internally disjoint if no vertex of is an internal vertex of more than one path in the family.

• (Wilson 28.3) A graph is -edge connected if and only if two distinct vertices of are connected by at least -edge disjoint paths

• (Wilson 28.4) A graph with at least vertices is -connected if and only if two distinct vertices of are connected by at least vertex disjoint paths.

Cycle §

• A cycle is a graph that is connected and 2-regular.

• A cycle is in a graph if .

  • A cycle is a trail where each vertex is distinct except for the first and last vertex.

• A cycle of vertices is denoted . is the length of the cycle.

• The girth of an undirected graph is the length of the shortest cycle in .

• (Wilson 6.1) If is a finite graph in which the degree of each vertex is at least , then contains a cycle.

• (Wilson e5.11a) If two distinct cycles of a graph each contain edge , then has a cycle that does not contain ¹

Triangles §

• A triangle-graph is the complete graph .

• A graph that does not contain a triangle is triangle-free

• Mantel’s Theorem ² Let be triangle free.

  If , then .

• (Wilson e5.10): The triangle free graph with vertices and edges is . ³

Eulerian Graphs §

• An Eulerian Trail is a trial in an undirected graph that visits every edge exactly once.

• An Eulerian Cycle is an Eulerian trail that starts and ends on the same vertex.

• A graph is Eulerian if it contains an Eulerian Cycle.

• A graph is Semi-Eulerian if it contains an Eulerian trail but not an Eulerian Cycle

• (Wilson 6.2) Euler’s Theorem: A connected graph is Eulerian if and only if the degree of each vertex of is even.

• (Wilson 6.3) A connected graph is Eulerian if and only if its set of edges can be split into disjoint cycles.

• (Wilson 6.4) A connected graph is Semi-Eulerian if and only if it has exactly two vertices of odd-degree.

Hamiltonian Graphs §

• A Hamiltonian Path is a path contained within a graph such that it passes through vertex exactly once.

• A Hamiltonian Cycle is a cycle contained within a Graph such that it passes through each vertex exactly once.

• A Hamiltonian Graph is a graph which contains a Hamiltonian Cycle

• A graph is Semi-Hamiltonian if it contains a Hamiltonian Path but not a Hamiltonian Cycle

• (Bondy and Murty 4.2) If is Hamiltonian, then for every non-empty .

• (Bondy and Murty 4.3) Dirac’s Theorem. If is a graph with vertices and then is Hamiltonian.

• (Wilson 7.1) Ore’s Theorem ³. Let be a simple graph with vertices. If for each pair of non-adjacent vertices and , then is Hamiltonian

Shortest Paths §

• Let be a weighted graph. The shortest path is the path between two vertices and that has a minimum weight.

  In an unweighted graph, this reduces to the path with the minimum number of vertices.

Links §

• Wilson

• Bondy and Murty

• Graph Connectivity

• Families of Graphs

• Directed Graph

Footnotes §

1. Consider the -path that goes from and then the -path in . ↩

2. The proof is by induction. Given a triangle free graph, perform an edge deletion on to get a smaller triangle-free graph. Show we can choose at most vertices to join to one of but not both. This implies, there are at most vertices not in the smaller graph. This will completes the proof. ↩

3. Given an edge , we may partition the remaining vertices into sets if they are connected to or . ↩ ↩²