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: Kn, Cn, Wn, Kn,m. Know shorthand, full names, structure, numbers of vertices and edges. Beware: Wn 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.