Решить 2 задачи по теории графов

1. Пусть G = (V,E) – граф без изолированных вершин. Докажите, что
а) если |E| ? |V| – 1, то существует связный граф с множеством вершин V и такими же
степенями вершин как у G;
б) если |E| ? |V| – 1, то существует лес с множеством вершин V и такими же степенями
вершин как у G.
в) если |E| = |V| – 1, то существует дерево с множеством вершин V и такими же степенями
вершин как у G;

2. Верно ли, что в любом вершинно k-связном графе для любых его попарно различных
вершин A. B. V1, V2, … , Vk-1 существует (A,B)-цепь, содержащая все вершины V1, V2, … , Vk-1?