Graphs

Assignment

Problems from Mathematics for Computer Science (MCS). These are tentative, I will probably remove a few after working them out myself.

1. MCS Problem 12.2, but instead of 20, use (first two letters of your last name, add them up, % 10, *2, +10). Kinne: Ki, 10+8, 18, %10 = 8, *2 = 16, +10 = 26. Note: simple graph is unweighted, undirected, no self loops.
2. MCS Problem 12.12 (ungraded). Bipartite: 2 parts.
3. MCS Problem 12.23 and note that Chi(G) is the chromatic number of G - the smallest number of colors that can be used to color the vertices of the graph.
4. MCS Problem 12.25. Connected component - can get from any vertex in the component to any other in the component, and cannot go outside the component.
5. MCS Problem 12.33
6. MCS Problem 12.46. Base case: 1 vertex graph, 2 vertex graph, 3 vertex graph.
7. MCS Problem 12.50. Diameter - largest distance between any two vertices. Note - "degrees of separation", "Erdos number".