Combinatorics

11.2.11.1

• The only edge incident with \(\displaystyle a\) is \(\displaystyle e_1\text{,}\) so the valency of \(\displaystyle a\) is \(\displaystyle 1\text{.}\)

• The only edge incident with \(\displaystyle b\) is \(\displaystyle e_2\text{,}\) so the valency of \(\displaystyle b\) is \(\displaystyle 1\text{.}\)

• The edges incident with \(\displaystyle c\) are \(\displaystyle e_1\text{,}\) \(\displaystyle e_3\text{,}\) and \(\displaystyle e_4\text{,}\) so the valency of \(\displaystyle c\) is \(\displaystyle 3\text{.}\)

• The edges incident with \(\displaystyle e\) are \(\displaystyle e_4\text{,}\) \(\displaystyle e_5\text{,}\) and \(\displaystyle e_6\text{,}\) and \(\displaystyle e\) appears twice as an endvertex of \(\displaystyle e_6\text{,}\) so altogether \(\displaystyle e\) appears \(\displaystyle 4\) times as the endvertex of some edge. Thus, the valency of \(\displaystyle e\) is \(\displaystyle 4\text{.}\)

• The edges incident with \(\displaystyle e\) are \(\displaystyle e_4\text{,}\) \(\displaystyle e_5\text{,}\) and \(\displaystyle e_6\text{,}\) so the valency of \(\displaystyle e\) is \(\displaystyle 3\text{.}\)

Since \(\displaystyle e_6 = \{e,e\}\) is a loop, the graph is not simple. There is no isolated vertex, because no vertex has valency \(\displaystyle 0\text{.}\) The only neighbour of \(\displaystyle a\) is \(\displaystyle c\text{,}\) and the only edge incident with \(\displaystyle a\) is \(\displaystyle e_1\text{.}\)

11.2.11.3

• The edges incident with \(\displaystyle a\) are \(\displaystyle e_1\) and \(\displaystyle e_2\text{,}\) so the valency of \(\displaystyle a\) is \(\displaystyle 2\text{.}\)

• The edges incident with \(\displaystyle b\) are \(\displaystyle e_1\) and \(\displaystyle e_3\text{,}\) so the valency of \(\displaystyle b\) is \(\displaystyle 2\text{.}\)

• The edges incident with \(\displaystyle c\) are \(\displaystyle e_2\) and \(\displaystyle e_3\text{,}\) so the valency of \(\displaystyle c\) is \(\displaystyle 2\text{.}\)

• No edges are incident with \(\displaystyle d\text{,}\) so the valency of \(\displaystyle d\) is \(\displaystyle 0\text{.}\)

There are no loops or multiple edges, so the graph is simple. The graph does have an isolated vertex, namely, \(\displaystyle d\) (because the valency of \(\displaystyle d\) is \(\displaystyle 0\)). The neighbours of \(\displaystyle a\) are \(\displaystyle b\) and \(\displaystyle c\text{,}\) and the edges incident with \(\displaystyle a\) are \(\displaystyle e_1\) and \(\displaystyle e_2\text{,}\) as was already mentioned above.

11.3.13.3 In the following picture, the dotted line represents the edge we will delete. If we then delete the white vertex, the graph that remains is complete. If instead we then delete the large grey vertex (which is the next one clockwise from the white vertex), the remaining graph will not be complete, since the white vertex is only adjacent to four of the five black vertices.

11.3.13.4 Proof. Let \(\displaystyle G\) be a graph with \(\displaystyle e\) edges.

Base case: \(\displaystyle e=0\text{.}\) Since \(\displaystyle G\) has no edges, every vertex has valency \(\displaystyle 0\text{.}\) So the number of vertices of odd valency is \(\displaystyle 0\text{,}\) which is even.

Inductive step: We begin with the inductive hypothesis. Fix \(\displaystyle e \ge 0\text{,}\) and assume that every graph with \(\displaystyle e\) edges has an even number of vertices of odd valency.

Now we want to deduce that every graph with \(\displaystyle e+1\) edges has an even number of vertices of odd valency. Let \(\displaystyle H\) be an arbitrary graph with \(\displaystyle e+1\) edges. Choose one edge \(\displaystyle f\) (there is one since \(\displaystyle e+1 \ge 1\)), and call its endvertices \(\displaystyle u\) and \(\displaystyle v\text{.}\) Let \(\displaystyle H'=H\setminus\{f\}\text{.}\) Notice that \(\displaystyle H'\) has \(\displaystyle e+1-1=e\) edges, so our induction hypothesis applies to \(\displaystyle H'\text{.}\) Therefore, \(\displaystyle H'\) has an even number of vertices of odd valency. Call this number \(\displaystyle 2m\text{,}\) where \(\displaystyle m \in \mathbb Z\text{.}\)

Observe that the valency of every vertex of \(\displaystyle H\) is the same as its valency in \(\displaystyle H'\) if the vertex is not \(\displaystyle u\) or \(\displaystyle v\text{,}\) and is one greater than its valency in \(\displaystyle H'\) if the vertex is either \(\displaystyle u\) or \(\displaystyle v\text{.}\) Consider the three possible cases: \(\displaystyle u\) and \(\displaystyle v\) both have even valency in \(\displaystyle H'\text{;}\) \(\displaystyle u\) and \(\displaystyle v\) both have odd valency in \(\displaystyle H'\text{;}\) or exactly one of \(\displaystyle u\) and \(\displaystyle v\) has even valency in \(\displaystyle H'\text{.}\)

If \(\displaystyle u\) and \(\displaystyle v\) both have even valency in \(\displaystyle H'\text{,}\) then they both have odd valency in \(\displaystyle H\text{,}\) so the number of vertices of odd valency in \(\displaystyle H\) must be \(\displaystyle 2m+2\text{,}\) which is even.

If \(\displaystyle u\) and \(\displaystyle v\) both have odd valency in \(\displaystyle H'\text{,}\) then they both have even valency in \(\displaystyle H\text{,}\) so the number of vertices of odd valency in \(\displaystyle H\) must be \(\displaystyle 2m-2\text{,}\) which is even.

If exactly one of \(\displaystyle u\) and \(\displaystyle v\) has even valency in \(\displaystyle H'\text{,}\) then exactly one of \(\displaystyle u\) and \(\displaystyle v\) will have even valency in \(\displaystyle H\) (the other one, since the valency of each of \(\displaystyle u\) and \(\displaystyle v\) goes up by \(\displaystyle 1\)). So the number of vertices of odd valency in \(\displaystyle H\) must be \(\displaystyle 2m\) (even though one of the specific vertices of odd valency has changed between \(\displaystyle u\) and \(\displaystyle v\)), which is even.

In all cases, \(\displaystyle H\) has an even number of vertices of odd valency. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, every graph with at least \(\displaystyle 0\) edges has an even number of vertices of odd valency. ◾

11.4.7.1 The graphs are not isomorphic, because the only vertex of valency \(\displaystyle 1\) in \(\displaystyle G\) (namely, \(\displaystyle c\)) is adjacent to a vertex of valency \(\displaystyle 3\) (namely \(\displaystyle d\)), but the only vertex of valency \(\displaystyle 1\) in \(\displaystyle H\) (namely, \(\displaystyle z\)) is adjacent only to a vertex of valency \(\displaystyle 2\) (namely, \(\displaystyle y\)).

Here is a more complete proof. Suppose \(\displaystyle \varphi \colon G \to H\) is an isomorphism. (This will lead to a contradiction.) We must have

(This principle was pointed out in the proof of Proposition 11.4.4.3.) The only vertex of valency \(\displaystyle 1\) in \(\displaystyle H\) is \(\displaystyle z\text{,}\) so this implies that \(\displaystyle \varphi(c) = z\text{.}\)

Now, since \(\displaystyle d \sim c\text{,}\) we must have \(\displaystyle \varphi(d) \sim \varphi(c)\text{.}\) Since \(\displaystyle \varphi(c) = z\text{,}\) and the only neighbour of \(\displaystyle z\) is \(\displaystyle y\text{,}\) this implies \(\displaystyle \varphi(d) = y\text{.}\) SoHowever, \(\displaystyle d_H(y) = 2\) and \(\displaystyle d_G(d) = 3\text{,}\) so \(\displaystyle d_H(y) \neq d_G(d)\text{.}\) This is a contradiction.

11.4.7.3 There is no vertex of valency \(\displaystyle 0\) in \(\displaystyle G_1\text{,}\) but \(\displaystyle A\) is a vertex of valency \(\displaystyle 0\) in \(\displaystyle G_2\text{.}\) Therefore \(\displaystyle G_1\) and \(\displaystyle G_2\) do not have the same degree sequence, so they are not isomorphic.

11.4.8.2 Of the five vertex labels, we can choose any two to join with an edge. Thus, the number of labeled graphs on five vertices with one edge is \(\displaystyle \binom{5}{2}=10\text{.}\)

11.4.8.3 Notice that there are \(\displaystyle \binom{5}{2}=10\) total edges possible in a graph on \(\displaystyle 5\) vertices. Thus, the number of labeled graphs on \(\displaystyle 5\) vertices with \(\displaystyle 3\) edges is the number of ways of choosing \(\displaystyle 3\) of these \(\displaystyle 10\) labeled edges. So there are \(\displaystyle \binom{10}{3}=120\) labeled graphs on \(\displaystyle 5\) vertices that have \(\displaystyle 3\) edges.

Similarly, there are \(\displaystyle \binom{10}{4}=210\) labeled graphs on \(\displaystyle 5\) vertices that have \(\displaystyle 4\) edges. Thus, in total there are \(\displaystyle 120+210=330\) labeled graphs on \(\displaystyle 5\) vertices that have \(\displaystyle 3\) or \(\displaystyle 4\) edges.