April 29th

Graph Isomorphism. Two graphs are isomorphic when there is a one-to-one mapping from the vertices of the first graph to the vertices of the second graph which preserves the edges.

More plainly, isomorphic graphs are basically the same. If I can redraw and relabel one graph and make it match another graph then they are isomorphic. As a child of the computer age you could imagine it as dragging vertices of one graph around to make it look like another graph.

At this stage you can detect non-isomorphism by finding chains of vertices in one graph that can't exist in the other (think about degree sequences). You can detect isomorphism my finding a specific mapping from one graph to the other. Isomorphisms are equivalence relations and thus partition all graphs. (It is a difficult problem to generally decide if two graphs are isomorphic or not.)


I want you to do 1 - 11 from 9.3, it's tough to display them here. Bust out the books, I might make copies.

Also, how many 6 digit numbers have 3 digits of one value, 2 digits of another value and 1 digit of a third value? (They don't start with 0.)

The true size of your problems.