CS 173: Skills list for Examlet 5

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, and K_n,m is not the same thing as a normal complete graph.
• Walks: walk, open walk, closed walk, cycle, path.
• Connectivity: connected graph, connected component, cut edge, acyclic.
• Distances: length of a path (number of edges in it), distance between two nodes, diameter of a graph.
• 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.
• 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.

Collections of sets

• Write simple proofs involving collections of sets and/or functions whose input and/or output values are sets.
• Interpret definitions for functions whose input and/or output values are sets (i.e. when the domain and/or co-domain is a power set).
• Interpret set-builder definitions of sets containing other sets.
• Given a specific set A, list the elements of its power set.
• Define the power set (A) for a set A.
• Manipulate sets containing other sets using standard set operations. (Be careful of getting the right number of brackets in examples involving the empty set and sets with only one element.)

Counting

• Know the definition of the factorial function (n!).
• Know the shorthand notation for binomial coefficients (number of combinations) and its definition in terms of factorials.
• Know the formula for computing the number of combinations of k objects from n types, with repetition.
• Know the Binomial Theorem and Pascal's Identity.
• Be able to solve practical counting problems involving combinations, combinations with repetition, and applications of the Binomial Theorem.
• Correctly decide whether to apply a permutation formula vs. a combination formula.