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 _{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}{ccccc}& 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.