- 1 In Each Part Either Give An Example Of A Graph Meeting The Stated Condition S Or Explain Why Such A Graph Cannot Ex 1 (93.34 KiB) Viewed 49 times
1. In each part, either give an example of a graph meeting the stated condition(s) or explain why such a graph cannot ex
-
- Site Admin
- Posts: 899559
- Joined: Mon Aug 02, 2021 8:13 am
1. In each part, either give an example of a graph meeting the stated condition(s) or explain why such a graph cannot ex
1. In each part, either give an example of a graph meeting the stated condition(s) or explain why such a graph cannot exist. (a) A graph with 7 vertices whose degrees are 5, 5, 3, 2, 2, 2, 2. (b) A 3-regular graph with 7 vertices. (c) A disconnected regular graph. (d) A disconnected graph with 10 vertices and minimum degree 5. (e) A graph with no two vertices of the same degree. 2. Suppose that a graph G has 25 vertices and 62 edges. Suppose further that there are 2 vertices with degree 4, 11 vertices of degree 6, and that every other vertex has degree 3 or 5. How many vertices in G have degree 3? (Do not try to draw G!) 3. (a) Suppose that a d-regular graph has n vertices and 5 edges. Solve for d in terms of n (b) Use part (a) to show that there are only 2 non-isomorphic regular graphs with 5 edges. 4. Use the method outlined in Section 2.2 to find a 3-regular graph H that contains the following graph G as an induced subgraph: