CS 173: Skills list for Examlet 5
- Simple Graphs
- Define these terms, and apply the definitions: cycle, degree, adjacent, distance, bipartite, connected, (a)cyclic.
- Construct graphs meeting a given specification.
- Determine if two graphs are isomorphic, and prove properties of isomorphic graphs.
- Define and prove properties of the graphs Kn, Ln, Cn, and Wn.
- Prove properties of colorings and chromatic numbers.
- Trees
- Know that a tree is defined as a connected acyclic graph.
- Know that a tree has exactly |V(G)|-1 edges: any graph with fewer is not connected, and any graph with more is cyclic.
- Define these terms for directed trees, and apply the definitions: root, parent, child, height.