6.6 Exercises

1.

If $G$ is a graph with at $n$ vertices and at most $nk/2$ edges, then $\alpha(G)\geq n/(k+1)$ .
2.

Show that any bipartite graph with maximum degree $d$ is a union of $d$ matchings.
3.

A tree $T$ has a perfect matching iff $o(T-v)=1$ for all $v\in T$ .
4.

Show that $2\alpha^{\prime}(G)=\min_{S\subset V}\{|V(G)|-d(S)\}$ where $d(S)=o(G-S)-|S|$ .
5.

For any $k$ , show that there are $k$ -regular graphs with no perfect matching.
6.

If G is $k$ -regular, has even number of vertices and remains connected when any $(k-2)$ edges are deleted, then G has a $1$ -factor.
7.

Let G be a k-regular bipartite graph. Prove that G can be decomposed into r-factors iff r divides k.
8.

Is it true that every tree has at most one perfect matching ?
9.

Let $T$ be a tree on $n$ vertices such that $\alpha(T)=k$ . Can you determine $\alpha^{\prime}(T)$ in terms of $n, k$ ?
10.

Every $3$ -regular graph with no cut-edge has a $1$ -factor.

1.

Let $Q_{n}$ be the hypercube graph on ${0,1}^{n}$ . What are $\alpha(Q_{n}),\alpha^{\prime}(Q_{n}),\beta(Q_{n}),\beta^{\prime}(Q_{n})$ ?
2.

Every 3-regular simple graph with no cut-edge decomposes (i.e., edge-disjoint union) into copies of P4 (the 4-vertex path).
3.

Characterize the graphs $G$ for which the following statements hold. Justify your answers.
(1) (max. independent set) $\alpha(G)=1$ .
(2) (max. size of matching) $\alpha^{\prime}(G)=1$ .
(3) (min. vertex cover) $\beta(G)=1$ .
(4) (min. edge cover) $\beta^{\prime}(G)=1$ .
NOTE : In each of the above, you are required to prove a statement of the form $\ldots(G)=1$ iff $G$ is $\ldots$ .