1.1(a). 15

(b) N (v1 ) = {v4 ,v7 } and d(v1 ) = 2

N (v5 ) = {v3 ,v4 ,v6 } and d(v5 ) = 3

δ(G) = 2 (both v1  and v8  have degree 2, while other degrees are higher) ∆(G) = 6 (v3  has degree 6, while other degrees are smaller)

(c) 5

(e) K4:

(d) 2         (see drawings)

v1

v7 v2

v5               v4

v9

v8

(d)

v2

v6

v5               v4

v9

v8

– We would need 4 vertices all adjacent, so each would have degree > 3 in the original graph. So remove vertices v1 ,v8 ,v9. This leaves v2 ,...,v7 .

– v2  is adjacent to v3 ,v6 ,v7 , but they don’t form a K4, since {v3 ,v6 } isn’t an edge.  So v2  can’t be in a K4 .

– In the same way, we can also eliminate v2 ,v7 ,v4 ,v5 , leaving just v3  and v6 , which isn’t enough vertices for a K4. So there is no K4  in this graph.

K1,7 :  We would need a vertex of degree > 7 to use for the part of size 1, but the max degree is 6, so there is no K1,7 .

K2,3 : Yes! There are at least two solutions.

1st solution: A = {v3 ,v6 } (red) and B = {v2 ,v5 ,v7 } (blue).

2nd solution: A = {v4 ,v7 } (red) and B = {v1 ,v3 ,v6 } (blue).

Form the graph H with vertices A u B and all 6 edges {a, b} with a e A and b e B . These are subsets of the vertices and edges of the original graph, so H is a subgraph of G. Thus, K2,3  is a subgraph of G.

Note: In the first solution, the induced subgraph G[A u B] = G [{v2 ,v3 ,v5 ,v6 ,v7 }] is not a K2,3 , since it has an edge {v2 ,v7 } (shown dotted) between two vertices of B .  However, on removing that edge, we get H described above, which is a subgraph of G and is a K2,3 .

v1

v7 v2                            v7

v3

v5

(f) A longest cycle is v1 ,v7 ,v2 ,v6 ,v5 ,v3 ,v4 ,v1  of length        (has 7 edges).   There are other

solutions as well, including or reversing this solution, and possibly others.  A cycle cannot simultaneously include vertices right of v3  and also left of v3  because it would have to go through v3  twice. Since this uses v3  and all vertices left of it, it’s the longest possible.

A longest path is v1 ,v4 ,v5 ,v6 ,v7 ,v2 ,v3 ,v8 ,v9  of length      . This uses all vertices, so it’s

the longest possible.

(g)

v

v9

v3            v8

1.2. If it’s a wheel graph, we can label the vertices as requested so that the cycle is v2 ,...,vn, while the vertex adjacent to all vertices of the cycle is labelled v1 .

With this numbering, we should have d(v1 ) = n - 1 (because it’s adjacent to the n - 1 vertices in the cycle), and d(vi) = 3 for i = 2,...,n (because each vi is adjacent to two vertices in the cycle, and also to v1 ). While these degrees are necessary if it’s a wheel graph, they may not be sufficient; it’s not guaranteed that any graph with those degrees is a wheel graph.

Left graph: The center vertex has degree 7 - 1 = 6, so it has to be v1 , while the other vertices have degree 3. However, removing v1  and its edges gives two triangles (two 3-cycles) instead of one 6-cycle. So, it’s

Right graph: The vertex on the far right has to be v1 , since it has degree 7 - 1 = 6, while the others have degree 3. Removing v1  and its edges (pink in the diagram below) gives a cycle (black), so this is a wheel graph.  There are actually 12 different ways to number the vertices in the cycle as v2 ,...,v7 :  Pick any of them to be v2  (6 choices of where to start).  Go around the cycle from there in either direction (2 choices), consecutively numbering the other 5 vertices v3 ,...,v7.  The total number of ways is 6 · 2 = 12. One way is shown below.

v6

v1

v5

1.3. An example grid graph is shown in the textbook (Figure 1.3).

Vertices: There is an array of n vertices high by n vertices across, giving |V | = n2 .

Edges:  Since the coordinates are integers, the condition (x - x/)2 + (y - y/)2  = 1 means that either x = x/  and |y - y/| = 1 (vertical edges) or y = y/  and |x - x/| = 1 (horizontal edges).

The grid has n columns of vertical edges, each with n - 1 vertical edges in it.  Thus, there are n(n - 1) vertical edges.  Similarly, it has n(n - 1) horizontal edges.  The total number of edges is |E| = 2n(n - 1).

1.6. (a) Method 1: Most students will probably do it like this; we’ll explain for C4:

● For C4, the vertices are 1, 2, 3, 4, and the edges are 12, 23, 34, 41.

● For L(C4), draw vertices named 12, 23, 34, 41.

● Draw edges between all pairs of these that share a character (representing a vertex in the original graph), so 12 - 23, 23 - 34, 34 - 41, and 41 - 12.

Method 2:  Method 1 doesn’t say where to draw the vertices.  This second method gives a specific place to draw them, based on the drawing of G:

● Draw the original graph G in black. We will superimpose the line graph on it in red.

● Draw a red vertex along each black edge (usually at the center, unless there’s a conflict). The red vertices are the vertices of the line graph. Name them the same as the edges of G that they represent.

● When two edges of G (in black) meet at a vertex of G (in black), connect their red vertices together by a red edge (added to the line graph).

● Remove the black graph and keep the red graph only. This is the line graph!

1          2

4          3 C4

1

2 K4

1   12  2

4   34  3

1

3      23     2

12

14 23

34

L(C4)

14

13            12

(b) Method  1:  If e and f  are distinct edges in G with a nonempty intersection, then the intersection has to be a set of one vertex of G: e n f = {v} for some v e V (G).

For each v e V (G), the number of edges in L(G) where e n f = {v} is /d )、. That is, pick any two out of the d(v) edges incident with v, and their interection will be {v}.

Sum over all v e V (G) to get the total number of edges in L(G):

Method 2: Continue evaluating the result from Method 1:

|E(L(G))| =   L   ╱d )、=   L /d(v)2 - d(v)、

3」

Method 3: The edges of G become the vertices of L(G), so E (G) = V (L(G)).

For each e e V (L(G)) (same as each e e E (G)), let D (e) denote the degree of vertex e in L(G). (The notation D(e) is shorter than dL(G)(e).)

Write e = {u, v}, where u v are vertices in G. Then d(u) - 1 edges f of G have e n f = {u}, and d(v) - 1 edges f of G have e n f = {v}. Thus, D (e) = D ({u, v}) = d(u)+ d(v) - 2.

The total number of edges of L(G) is half the sum of the degrees of the vertices in L(G):

1.9. Use S = {1,...,n} as the n-element set.

(a) The set of vertices is ,{1} ,..., {n}、.

All vertices are disjoint, so there are edges between all of them.

Thus, Kn:1  is equivalent to the complete graph Kn, but just labelled differently. (b) For K4:2: The set of vertices in K4:2  is

,{1, 2} , {1, 3} , {1, 4} , {2, 3} , {2, 4} , {3, 4}、.

Abbreviate {1, 2} by 12, etc.

Vertex 12 only has empty intersection with 34 (that is, {1, 2}n{3, 4} = 0), so 12 - 34 is an edge but 12 doesn’t form any other edges.

In the same way, all the edges are 12 - 34, 13 - 24, and 14 - 23.

12 34

13 24

14 23

K4:2

14

35 25

34

K5:2

For K5:2: The vertices are 12, 13, 14, 15, 23, 24, 25, 34, 35, 45.

For vertex  12  (meaning  {1, 2}), the vertices that have empty intersection with it are 34, 35, 45. So 12 is incident with three edges, 12 - 34, 12 - 35, 12 - 45.

In the same way, for vertex ab, the sets of size r = 2 disjoint from it are formed from choosing any r = 2 of the elements of {1,...,n}\{a, b}, which can be done in /52(_)2、= /2(3)、= 3 ways. So every vertex has degree 3.

A nice way to draw the graph is shown above; however, it is not necessary to draw it exactly like this. The vertices can be laid out in a completely different way that doesn’t show these symmetries.  Different drawings that don’t look alike can represent the same graph, as long as they have the same representation in the format G = (V, E).  Even with this drawing, due to the symmetries, there are many ways to place the vertex labels (5! = 120 ways by permuting the digits 1,..., 5).

(c)  Kn:r  has  /r(n)、vertices.

Consider any vertex A. It’s an r-element subset of S. The vertices disjoint from A are all r-element subsets of Ac  (the set complement of A, also denoted S \ A). Since |Ac | = n - r , there are /n r(_)r、vertices disjoint from A, and A forms an edge with each of them.

Thus, every vertex has degree  /n r(_)r、.

There are /r(n)、vertices, so the sum of degrees is /r(n)、· /n r(_)r、. This is double the number of

H-101.

(a) G = (V, E) where                                   V = {1, 2, 3, 4, 5, 6}

E = {(1, 2), (1, 3), (1, 5), (2, 4), (2, 6), (3, 6)}

Note that 1 is not a prime, so you should not include any edges of the form (i, i). Also, (1, 4) and (1, 6) are not edges because 4/1 = 4 and 6/1 = 6 are not prime.