#
CS 173, Fall 2014: Skills list for sixth examlet

- Graph basics
- Know that a graph is a set of vertices/nodes plus a set of edges.
- Know what a loop and a multi-edge are, that a "simple graph" has neither,
and that graphs in this class are simple unless we specify otherwise.
- Know how to name edges via their endpoints, e.g. vw or {v,w}.
- Be able to specify a walk using an edge sequence and/or node sequence.

- Graph terminology and notation
- Basics: adjacent/neighboring vertices, endpoints of an edge, edge connecting
(incident with) two vertices, degree of a vertex, subgraph
- Special example graphs:
K
_{n}, C_{n}, W_{n},
K_{n,m}. Know shorthand, full names, structure, numbers of vertices and edges.
Beware: W_{n} contains n+1 vertices.
- Walks: walk, open walk, closed walk, cycle, path.
- Connectivity: connected graph, connected component, cut edge, acyclic.
- Other facts and concepts: Euler circuit, Handshaking theorem, bipartite graph

- Graph properties
- Find the number of connected components in a graph
- Determine if a graph has an Euler circuit
(all vertices in the graph must have even degree).
- Count the number of paths between two fixed nodes

- Graph isomorphism
- Prove that two graphs are isomorphic by giving a bijection between their vertices.
- Count the number of isomorphisms between two graphs.
- Prove that two graphs are not isomorphic by finding a feature that differs, e.g. different numbers of nodes/edges,
different numbers of vertices with a specific degree k,
small subgraph present in one graph but not in the other.