Combinatorics

12.1.6.1 Proof. We prove, by induction on \(\displaystyle n\text{,}\) that if \(\displaystyle n \ge 1\text{,}\) and \(\displaystyle G\) is any digraph with \(\displaystyle n\) vertices that has no loops or multiarcs, then

Base case: \(\displaystyle n=1\text{.}\) Let \(\displaystyle G\) be a digraph with no loops or multiarcs, and with only one vertex \(\displaystyle v_1\text{.}\) Then there are no arcs in \(\displaystyle G\text{,}\) so \(\displaystyle |A(G)|=0=d^+_G(v_1)=d^-_G(v_1)\text{.}\) So the desired conclusion is true when \(\displaystyle n=1\text{.}\)

Inductive step: Assume that \(\displaystyle n\ge 1\text{,}\) the formula holds for every digraph with \(\displaystyle n\) vertices that has no loops or multiarcs, and \(\displaystyle G\) is a digraph with \(\displaystyle n + 1\) vertices that has no loops or multiarcs.

Pick an arbitrary vertex \(\displaystyle u\) of \(\displaystyle G\text{.}\) Let

• \(\displaystyle N^+\) be the set of outneighbours of \(\displaystyle u\text{,}\) and \(\displaystyle N^-\) the set of inneighbours of \(\displaystyle u\text{,}\)

• \(\displaystyle s = |N^+|= d^+_G(u)\) be the number of arcs that begin at \(\displaystyle u\text{,}\)

• \(\displaystyle t = |N^-|= d^-_G(u)\) be the number of arcs that end at \(\displaystyle u\text{,}\) and

• \(\displaystyle G'\) be the digraph obtained from \(\displaystyle G\) by deleting \(\displaystyle u\) and its \(\displaystyle s+t\) incident arcs.

Note that:

• \(\displaystyle V(G') = V(G) \smallsetminus \{u\}\text{,}\) so \(\displaystyle G'\) has \(\displaystyle n\) vertices.

• \(\displaystyle |A(G')| = |A(G)| - s-t\text{.}\)

• For \(\displaystyle v \in V(G') \smallsetminus N^-\text{,}\) we have \(\displaystyle d^+_{G'}(v) = d^+_G(v)\) (because the outneighbours of \(\displaystyle v\) in \(\displaystyle G'\) are exactly the same as the outneighbours of \(\displaystyle v\) in \(\displaystyle G\)).

• For \(\displaystyle v \in N^-\text{,}\) we have \(\displaystyle d^+_{G'}(v) = d^+_G(v) - 1\) (because \(\displaystyle u\) is counted as an outneighbour of \(\displaystyle v\) in \(\displaystyle G\text{,}\) but it is not in \(\displaystyle G'\) so it cannot be counted as an outneighbour in \(\displaystyle G'\)).

• Similar statements hold with \(\displaystyle N^-\) replaced by \(\displaystyle N^+\text{.}\)

Hence

Similarly, we can argue that \(\displaystyle \sum_{v \in V(G)}d^-G(v)=|A(G)|\text{.}\) This completes the inductive step and the proof. ◾

12.1.6.3 Beginning at the top and working clockwise, label the vertices of the digraph \(\displaystyle a\text{,}\) \(\displaystyle b\text{,}\) \(\displaystyle c\text{,}\) \(\displaystyle d\text{,}\) and \(\displaystyle e\text{.}\) Then:

• \(\displaystyle a\) has outvalency \(\displaystyle 2\) and invalency \(\displaystyle 1\text{;}\)

• \(\displaystyle b\) has outvalency \(\displaystyle 2\) and invalency \(\displaystyle 2\text{;}\)

• \(\displaystyle c\) has outvalency \(\displaystyle 1\) and invalency \(\displaystyle 2\text{;}\)

• \(\displaystyle d\) has outvalency \(\displaystyle 2\) and invalency \(\displaystyle 2\text{;}\)

• \(\displaystyle e\) has outvalency \(\displaystyle 1\) and invalency \(\displaystyle 1\text{.}\)

12.2.6.2 This graph is connected. To see this, note that \(\displaystyle (a,j,g,v,e,d,i,h,c,b)\) is a walk that passes through all of the vertices of \(\displaystyle G\text{,}\) so it is possible to walk from \(\displaystyle a\) to any other vertex. Therefore, the connected component that contains \(\displaystyle a\) is \(\displaystyle V(G) = \{a,b,c,d,e,f,g,h,i,j\}\text{.}\)

There are several walks of length \(\displaystyle 5\) from \(\displaystyle a\) to \(\displaystyle f\text{.}\) One example is \(\displaystyle (a,g,a,j,g,f)\text{.}\)

12.2.6.3 This graph is not connected. To see this, note that there are no edges from any vertex in \(\displaystyle \{a,d,e,f,g,j\}\) to any vertex in \(\displaystyle \{b,c,h,i\}\text{.}\) Indeed the connected component that contains \(\displaystyle a\) is \(\displaystyle \{a,d,e,f,g,j\}\text{.}\) (The walk \(\displaystyle (a,d,e,f,g,j)\) passes through all of these vertices, but none of these vertices are adjacent to any vertex that is not in the subset.)

There are several walks of length \(\displaystyle 3\) from \(\displaystyle a\) to \(\displaystyle d\text{.}\) One example is \(\displaystyle (a,d,a,d)\text{.}\)

12.3.10.1

1. There are many paths of length 3. One example is \(\displaystyle (a,b,c,h)\text{.}\)

2. \(\displaystyle (b,c,f,b)\) is a cycle of length \(\displaystyle 3\text{.}\)

3. \(\displaystyle (a,b,c,b)\) is neither a path nor a cycle. It is not a path because the vertices are not all distinct. (Namely, the vertex \(\displaystyle b\) occurs twice.) It is not a cycle, because the first vertex (namely, \(\displaystyle a\)) is not the same as the final vertex (namely, \(\displaystyle b\)).

12.3.10.3 Proof. Let \(\displaystyle (u=u_1,u_2, \ldots, v=u_k,u)\) be a cycle of \(\displaystyle G\) in which \(\displaystyle u\) and \(\displaystyle v\) appear as consecutive vertices. Let \(\displaystyle G'=G\setminus\{uv\}\text{.}\)

Let \(\displaystyle x\) and \(\displaystyle y\) be arbitrary vertices of \(\displaystyle G\text{.}\) Since \(\displaystyle G\) is connected, there is a walk \(\displaystyle (x=x_1, x_2, \ldots, x_m=y)\) from \(\displaystyle x\) to \(\displaystyle y\) in \(\displaystyle G\text{.}\) If this walk does not contain the edge \(\displaystyle uv\) then it is also a walk in \(\displaystyle G'\text{.}\) If it does contain the edge \(\displaystyle uv\text{,}\) then we can find some \(\displaystyle i\) with \(\displaystyle 1 \le i \le m-1\) such that either \(\displaystyle x_i=u\) and \(\displaystyle x_{i+1}=v\text{,}\) or vice versa. For every such \(\displaystyle i\text{,}\) replace the pair \(\displaystyle (x_i,x_{i+1})\) in the walk by either \(\displaystyle (u=u_1,u_2, \ldots, v=u_k)\) or \(\displaystyle (v=u_k,u_{k-1},\ldots, u=u_1)\) (as appropriate, depending on whether \(\displaystyle x_i=u\) or \(\displaystyle x_i=v\)). The result is a walk from \(\displaystyle x\) to \(\displaystyle y\) that does not use the edge \(\displaystyle uv\text{,}\) so is in \(\displaystyle G'\text{.}\) Since \(\displaystyle x\) and \(\displaystyle y\) were arbitrary vertices of \(\displaystyle G'\text{,}\) for any two vertices \(\displaystyle x\) and \(\displaystyle y\) of \(\displaystyle G'\) there is an \(\displaystyle x-y\) walk, so by definition, \(\displaystyle G'\) is connected. ◾

12.4.6.1 Proof. Let \(\displaystyle T\) be a tree, and let \(\displaystyle v\) be a leaf of \(\displaystyle T\text{.}\) Consider \(\displaystyle T\setminus\{v\}\text{.}\) Certainly it cannot have any cycles, since \(\displaystyle T\) has no cycles. Let \(\displaystyle x\) and \(\displaystyle y\) be arbitrary vertices of \(\displaystyle T\setminus\{v\}\text{.}\) Since \(\displaystyle T\) is connected, there is an \(\displaystyle x-y\) walk in \(\displaystyle T\text{,}\) so by Proposition 12.3.4, there is an \(\displaystyle x-y\) path in \(\displaystyle T\text{.}\) Since \(\displaystyle v\) is a leaf of \(\displaystyle T\text{,}\) if an \(\displaystyle x-y\) walk uses the vertex \(\displaystyle v\) then the neighbour of \(\displaystyle v\) would have to come both before and after \(\displaystyle v\) in the walk, since \(\displaystyle v\) has only one neighbour, so such a walk would not be a path. Thus, the \(\displaystyle x-y\) path cannot use the vertex \(\displaystyle v\text{,}\) so it is still a path in \(\displaystyle T\setminus\{v\}\text{.}\) Since \(\displaystyle x\) and \(\displaystyle y\) were arbitrary vertices, this shows that \(\displaystyle T\setminus\{v\}\) is connected. This completes the proof. ◾

12.4.6.3 The two nonisomorphic unlabeled trees on 4 vertices are: