# 15-344/Classnotes for Thursday September 17

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Lecture Notes for September 17

DEFINITION 7 Isomorphism A graph ${\displaystyle G_{1}=(V_{1},E_{1})}$ is called isomorphic to a graph ${\displaystyle G_{2}=(V_{2},E_{2})}$ whenever there exists a bijection ${\displaystyle \phi :V_{1}\rightarrow V_{2}}$ such that ${\displaystyle \forall a,b\in V_{1}}$ we have ${\displaystyle (ab)\in E_{1}}$ if and only if ${\displaystyle (\phi (a)\phi (b))\in E_{2}}$. ${\displaystyle G_{1}\sim G_{2}}$ means they are isomorphic to each other.

• Isomorphism does not mean two things are identical but means they are mathematically the same.

The relationship of isomorphisms:

1. Reflexive: ${\displaystyle G\sim G}$ A graph is isomorphic to itself

2. Symmetric: ${\displaystyle G_{1}\sim G_{2}\implies G_{2}\sim G_{1}}$ In other words, for every ${\displaystyle \phi :V_{1}\rightarrow V_{2}}$ we have ${\displaystyle \phi ^{-1}:V_{2}\rightarrow V_{1}}$

3. Transitive: ${\displaystyle G_{1}\sim G_{2},G_{2}\sim G_{3}\implies G_{1}\sim G_{3}}$

CLAIM If two graphs are isomorphic, then they have:

1. same number of vertices

2. same number of edges

3. vertex degrees (valencies) are the same between the two. For example, if one graph has 3 vertices of degree 2, and 2 vertices of degree 1, then the other graph should have the same

4. same number of subgraphs

5. same number of complements denoted by ${\displaystyle G^{c}=(V,E^{c})}$

• Complement means ${\displaystyle (ab)\in E^{c}\Longleftrightarrow (ab)\notin E}$

DEFINITION 8 Subgraph A subgraph of a graph ${\displaystyle G=(V,E)}$ is a graph ${\displaystyle G'=(V',E')}$ such that ${\displaystyle V'\subset V}$ and ${\displaystyle E'\subset E}$.

• Checking if two graphs are isomorphic is a hard problem