Graph isomorphism invariants.md

List of graph isomorphism invariants

This is a running list of graph isomorphism invariants, that is, properties of graphs such that...

If $G$ and $H$ are isomorphic and $G$ has the property, then $H$ also has the property.

A logically equivalent way to say this is:

If $G$ has the property but $H$ does not, then $G$ and $H$ are not isomorphic.

For example, "the number of vertices" is an invariant, so if $G$ and $H$ are isomorphic and $G$ has 99 vertices, $H$ must also have $99$ vertices. "Being connected" is an invariant; if $G$ and $H$ are isomorphic and $G$ is connected, then so is $H$.

Please note:

1. All of the items on the list below are true statements, and you can use any of them when doing work on a content Skill.
2. However, not all of these have been proven. If we have done a proof in class, this is indicated on the list. Items without in-class proofs may not be used in Proof Problem work unless you check with me (Talbert) first.
3. Items that do not appear on this list may not be used in your work unless you ask me first.
4. We will continue to add to this list as we learn more about graphs.

---

List of Invariants

• The number of vertices (proven in class notes for 2024-10-07)
• The number of edges (proven in class notes for 2024-10-07)
• The existence of a vertex with degree 4 (proven in class notes for 2024-10-07)
• The existence of a vertex with degree $n$ where $n$ is any nonnegative integer
• Degree sequence
• The number of vertices with a particular degree (For example, if $G$ has three vertices of degree 2 but $H$ has only one, then $G \not \cong H$.)
• Having a cycle of length $n$
• Being bipartite
• Being connected