Trails, Walks, Paths and Cycles

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.

• (Godsil e3.18) Any two paths of maximum length in a connected graph must have at least one vertex in common.

  • Proof: Let be the graph .Denote as a -path. By connectivity, is always well-defined. Also let and and such that both are maximum length paths.

    Let be the path . To choose and , we consider a path . is chosen to be the last vertex of in and the first vertex of in . This ensures that all the subpaths in are internally disjoint so that is a valid path. WLOG, assume and .

    By connectivity, and disjointness.

  and must have length at least . Therefore Therefore is a longer path which is a contradiction

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.

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

  • Proof: Consider the -path that goes from and then the -path in .

• (Godsil e3.19) Any two cycles of maximum length in a -connected graph must have at least three vertices in common

  • Proof: Let be the cycles of interest with length . By (Wilson 28.4), there must be at least vertex disjoint paths between and . Denote them as . We argue by contradiction and show that if , it is always possible to create a larger cycle. and must intersect at points and . We also let . respectively; Let be the part of the cycle containing bounded by and similarly for for , and for the other segments in the respective cycles

    First suppose that . .We create two new cycles.

    These cycles must have length but that would imply and which, from how we defined the paths implies .

    Now suppose where WLOG and . Consider the new cycles

    These cycles must have length but that would imply which would also imply .

    Now suppose . Where and and . It is possible to find a path connecting and without passing through and by -connectivity. Suppose they intersect the two cycles at and we define as before. WLOG, suppose and are the longer segments. Note that which implies . However, construct the cycle using these two segments. and This gives us a cycle of length completing the proof.

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. Then

  • Proof: 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 complete the proof.

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

  • Proof: Given an edge , we may partition the remaining vertices into sets if they are connected to or .

Links §

• Wilson

• Bondy and Murty

• Algebraic Graph Theory by Godsil and Royle

• Graph Connectivity

• Families of Graphs

• Directed Graph