# 15-344/Classnotes for Thursday September 17

## Lecture Notes for September 17

**DEFINITION 7 Isomorphism** A graph is called *isomorphic* to a graph whenever
there exists a bijection such that we have if and
only if . means they are isomorphic to each other.

- A
*bijection*is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection

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

The relationship of isomorphisms:

1. **Reflexive**: A graph is isomorphic to itself

2. **Symmetric:** In other words, for every we have

3. **Transitive:**

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

- Complement means

**DEFINITION 8** **Subgraph** A subgraph of a graph is a graph such that and
.

- Checking if two graphs are isomorphic is a hard problem