Mat332 Introduction to Graph Theory
Q3: Assume G is a connected graph
1. Suppose G is a graph of maximum vertex degree 3 with no isolated vertices.
(a) Determine the number of edges e(G) in terms of the numbers A, B, C of vertices in G of degrees 1, 2, 3 respectively.
(b) Suppose furthermore that G is a tree. Show that C = A - 2.
2. (a) Find a maximum matching and minimum vertex cover in the following graph:
(b) Suppose G is a bipartite graph that contains a collection C of 100 edges such that every vertex is contained in at least one edge of C, but there is no collection of 99 edges with this property. Determine the size of the largest independent set of vertices in G.
3. (a) Show that if a connected graph G contains a cycle C of length k and no path with k+1 vertices, then C is a Hamiltonian cycle.
(b) Show that if G is a connected 3-regular graph with |G| ≥ 7 then the longest path in G has at least 7 vertices.
4. Suppose G is a bipartite graph with no isolated vertices and bipartition X ப Y, with the property that whenever we select distinct vertices u, v ∈ X and y ∈ Y then at least one of uy or vy is an edge of G.
(a) Show that if |X| ≤ |Y| then there is an X-perfect matching
(b) Show that if |X| ≥ |Y| then there is a Y-perfect matching
5. (a) Construct a flow network with an edge e such that increasing the capacity of e by 5 increases the maximum flow of the network by 3.
(b) Suppose in a flow network there is an edge e with the property that increasing its capacity by 1 does not increase the value of the maximum flow. Show that increasing the capacity of e by 2 also does not increase the value of the maximum flow.
If you want to use a theorem about flow networks for this question you must use the version presented in class.