Definitions

• A graph is a pair \((V, E)\).
• Elements of \(V\) are vertices (or nodes)
• Elements of \(E\) are edges.
  • Directed / undirected.

Edit Distance

• Edit distance between two words
• Allowable operations:
  • Insert a letter
  • Delete a letter
  • Replace one letter with another
• Q: given words \(w_1\) and \(w_2\), how “far” apart are the letters?

Edit Distance

• Vertices: words (arbitrary strings of letters)
• Edges: if two words are one operation apart.
  • “cat” and “can”.
  • “met” and “meet”
• Now turned this into a “shortest path” problem.

Incidence

• A vertex \(v\) is incident to edge \(e\) if \(v\) is an endpoint of \(e\).
• Incidence matrix:
  • 1 row for each vertex
  • 1 column for each edge
  • entry \((i, j)\) is 1 if \(v_i\) is incident to \(e_j\).
  • if \(e_j\) is a self-loop at \(v_i\), then put a 2 instead.
  • 0 otherwise
  • Each column has at most 2 1’s.
• Many wasted 0s.

Example

Sum of Degrees

Theorem: The sum of the degrees of a graph equals \(2|E|\).

Proof:

• Represent the graph using an incidence matrix.
• \(deg(v_i) = \sum\limits_{j=1}^n a_{i,j}\) (row sum)
• Sum of degrees?
• column sum = \(2|E|\)
• row sum = column sum

Adjacency List

• \(v\) is adjacent to \(w\) if they share an edge.
• Adjacency list for \(v\): list of vertices adjacent to \(v\)
• Adjacency list representation of \(G\): table of all adjacency lists

Example

Adjacency Matrix

• Rows / columns are vertices
• Entry \((i, j)\) has a 1 iff edge between \(v_i, v_j\).

Example:

\[ \begin{array}{c|c|c|c|c} & v_1 & v_2 & v_3 & v_4 \\ v_1 & 0 & 1 & 0 & 0 \\ v_2 & 1 & 0 & 1 & 1 \\ v_3 & 0 & 1 & 0 & 0 \\ v_4 & 0 & 1 & 0 & 0 \end{array} \]

Definition

Let \(G = (V_G, E_G)\) and \(H = (V_H, E_H)\) be two undirected graphs. Then \(G\) and \(H\) are isomorphic if there is \(f : V_G \to V_H\) such that for all \(u, v \in V_G\), the number of edges between \(u\) and \(v\) is the same as the number of edges between \(f(u)\) and \(f(v)\).

\(f\) is called an isomorphism from \(G\) to \(H\).

• “iso”: same
• “morph”: form

Simple graphs

Two simple undirected graphs \(G\) and \(H\) are isomorphic if there is a bijection \(f : V_G \to V_H\) such that \(u\) and \(v\) are adjacent (in \(G\)) if and only if \(f(u)\) and \(f(v)\) are adjacent (in \(H\)).

Example

Are these graphs isomorphic?

Example

Are these graphs isomorphic?

Example

Are these graphs isomorphic?

Example

Structure

Look for isomorphism invariants:

• Number of vertices / edges
• Degree sequence
• Cycles of length \(n\)
• Connectivity (more later)
• Colorability
• Complement graph

Isomorphic graphs have the same properties. But none of these imply isomorphism!

Concept

• Isomorphic graphs are the same graph, structurally.
• Different representations of the same thing.
• Different names for vertices
• Different order of vertices.
• But they represent the same, underlying concept.

Automorphisms

• Let \(G = (V, E)\). An automorphism of \(G\) is an isomorphism from \(G\) to itself.
• Every graph has at least one: the identity.
  • \(id : V \to V\) given by \(id(v) = v\).
• A kind of “symmetry”.

Symmetries of S_3

Rigid

Deadlines

• Final Project:
  • Groups: today.
  • Pick a topic by Monday
  • Presentation 5/1
  • Paper due 5/8
• Final Exam: given 5/1, due 5/8
  • Possible extra help during finals week.