Math 137A Assignment 2

1. * Let A be the adjacency matrix of a graph G. Show that for every nonnegative integer k, the (vi, vj )-entry of A equals the number of walks of length k from vi to vj . Conclude that the number of triangles in G is

2. Prove that any simple graph G contains a path of length at least δ(G). (Recall that δ(G) is the minimum degree over all vertices in G.)

3. If G is a simple graph, the complement G is the graph with the same vertex set but vw ∈ E(G) if and only if vw ∈ E(G). Show that if G is disconnected, then G is connected and, moreover, there is always a path of length at most 2 between any two vertices in G.

4. Prove or disprove: There exists a connected Eulerian simple graph with an even number of vertices but an odd number of edges.

5. Prove or disprove: If G is a connected Eulerian graph with edges e, f sharing a common vertex, then G has an Eulerian circuit in which e and f appear consecutively.

6. (a) Prove that the average degree of any tree T is less than 2.

(b) If the average degree of a tree is 1.99, how many edges does the tree have?

(c) Conclude from Part (a) another proof that every tree with at least two vertices has a leaf.

7. Suppose that T is a tree with degree sequence (5, 4, 3, 2, 1, . . . , 1). How many 1’s are in the sequence?

8. For a graph G, ∆(G) denotes the maximum degree of G. For this question, prove that a tree T always has at least ∆(T) leaves.

9. Apply Kruskal’s algorithm to the graph in Figure 1 to find a minimum spanning tree (list out the edges in each step of the algorithm and draw the final MST.)

10. * Find a formula for τ (K2,n).