1. There is a connected graph with 8 vertices and 21 edges which has no
HC since 21 = (n − 1)(n − 2)/2 + 1 for n = 8. Is there such a graph if
we assume in addition that each vertex has degree at least 2? Please
provide one if it exists, or provide the argument if such graph does not
exist.
2. Show that a graph with 7 vertices and at least 17 edges has at least
two different HC – e.e different but at least one edge. ( note that
17 = (n − 1)(n − 2)/2 + 2 for n = 7)
3. Let G be a connected bipartite graph (i.e the set of vertices is split
as X
S
Y so that the edges are connecting some pairs xi ∈ X with
yj ∈ Y ). Show that if each vertex has multyplicity 3 then there is a
complete matching( i.e the number of vertices in X is the same as in
Y and there is matching of all vertices in X with vertices in Y )
4. Find a connected bipartite graph G with a minimal number of vertices
such that
(a) Each vertex has multyplicity either 3 or 4.
(b) X = Y where X and Y are as in the previous problem
(c) there is no complete matching
5. Describe all bipartite graphs modulo isomorphism with 12 vertices and
each vertex of degree 3.