CS 173, Fall 2015: 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.