5.4: Paths

Last updated
Save as PDF

Page ID: 88871

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Paths

Definition \(\PageIndex{1}\): Walk.

A graph is a walk if and only if the vertices can be labeled \(v_0, v_1, \ldots, v_k\) such that \(v_i, v_{i+1}\) is an edge.

Definition \(\PageIndex{2}\): Trail.

A graph is a trail if and only if it is a walk such that no edge is used twice.

Definition \(\PageIndex{3}\): Path.

A graph is a path if and only if it is a walk such that no vertex is used twice.

A path on \(n\) vertices is denoted \(P_n.\) Please note that these terms (walk, trail, and path) vary widely including reversing the names, so always check the definition in the article, book, or other material you are reading.

Definition \(\PageIndex{4}\): Eulerian Trail.

A trail is Eulerian if and only if it uses every edge in the graph.

Definition \(\PageIndex{5}\): Hamiltonian Path.

A path is Hamiltonian if and only if it uses every vertex in that graph.

Practice

Checkpoint \(\PageIndex{6}\)

Draw a path of length 5. Note this is denoted \(P_5.\)

Figure \(\PageIndex{7}\) Graph Containing Walks, Trails, and Paths

Checkpoint \(\PageIndex{8}\)

Find a walk that is not a trail in Figure \(\PageIndex{7}\)

Checkpoint \(\PageIndex{9}\)

Find a trail that is not a path in Figure \(\PageIndex{7}\)

Checkpoint \(\PageIndex{10}\)

Determine which graphs in Figure 5.2.43 have Eulerian trails.

Checkpoint \(\PageIndex{11}\)

Determine which graphs in Figure 5.2.43 have Hamiltonian paths.

Connected

Definition \(\PageIndex{12}\): Vertex Connected.

A graph \(G\) is connected if and only if for every pair of vertices \(v,w\) there exists a path from \(v\) to \(w.\)

Definition \(\PageIndex{13}\): Vertex \(n\)-connected.

A graph \(G\) is \(n\)-connected if and only if removing any \(n-1\) vertices does not disconnect the graph.

Practice

Checkpoint \(\PageIndex{14}\)

Determine which of the graphs in Figure 5.1.1 are connected.

Checkpoint \(\PageIndex{15}\)

Explain why every complete graph is connected.

Checkpoint \(\PageIndex{16}\)

Explain why every complete bipartite graph is connected.

Checkpoint \(\PageIndex{17}\)

Determine if every bipartite graph must be connected.

Checkpoint \(\PageIndex{18}\)

For each of the graphs in Figure 5.2.43 and Figure 5.2.44 determine the maximum \(n\) for which the graph is \(n\)-connected.

Checkpoint \(\PageIndex{19}\)

If a graph is \(n\)-connected what does this say about the minimum of the number of paths between any two vertices?