Exercise 7.1 Graph Definition
Find the number of vertices, the number of edges, and the degree of each vertex in the given undirected graph. Identify all isolated and pendant vertices.
Exercise 7.2 Graph Definition
How many vertices and how many edges do these graphs have? a) Kn
b) Cn
c) Wn
d) Km,n
e) Qn
Exercise 7.3 K-regular Graph
A simple graph is called regular if every vertex of this graph has the same degree. A regular graph is called n-regular if every vertex in this graph has degree n.
For which values of n are these graphs regular? a) Kn
b) Cn
c) Wn
d) Qn
e) For which values of m and n is Km,n regular?
Exercise 7.4 Isomorphism
Determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism or provide a rigorous argument that none exists.
a)
b)
c)
Exercise 7.5 Handshaking Theorem
Show that the sum, over the set of people at a party, of the number of people a person has shaken hands with, is even. Assume that no one shakes his or her own hand.
Exercise 7.6 Hall’s Theorem
Suppose that there are five young women and six young men on an island. Each woman is willing to marry some of the men on the island and each man is willing to marry any woman who is willing to marry him. Suppose that Anna is willing to marry Jason, Larry, and Matt; Barbara is willing to marry Kevin and Larry; Carol is willing to marry Jason, Nick, and Oscar; Diane is willing to marry Jason, Larry, Nick, and Oscar; and Elizabeth is willing to marry Jason and Matt.
a) Model the possible marriages on the island using a bipartite graph.
b) Find a matching of the young women and the young men on the island such that
each young woman is matched with a young man whom she is willing to marry.
c) Is the matching you found in part (b) a complete matching? Is it a maximum matching?
Exercise 7.7 Subgraph
1. How many subgraphs with at least one vertex does K2 have?
2. How many subgraphs with at least one vertex does K3 have?
3. How many subgraphs with at least one vertex does W3 have?
Exercise 7.8 Bipartition
Show that if G is a bipartite simple graph with v vertices and e edges, then e≤v2/4.
