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 are true statements, and you can use any of them when doing work on a Content Skill Standard quiz (particularly for Standard G.4).
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 first.
3. Items that do not appear on this list may not be used in your work unless you ask me first. Some of these appeared in your class notes as possibly being invariant properties, but we did not prove or disprove them, so just because you saw something on the Jamboard doesn't mean you can use it as a fact!
4. We will continue to add to this list as we learn more about graphs.

---

The List of Invariants

• The number of vertices (Proven in class on Wednesday 2022-09-28)
• The number of edges (Stated as true in class on 2022-09-28 but not proven; go ahead and use it if you want)
• The existence of a vertex with degree 2 (Proven in class on Wednesday 2022-09-28)
• The existence of a vertex with degree $n$ where $n$ is any nonnegative integer (Stated as true in class on 2022-09-28 but not proven; go ahead and use it if you want)
• Degree sequence (To be proven in Proof Problem 8, but it's so useful that you can go ahead and use it even if you don't prove it.)
• 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$. We'll probably not prove this, but it's true and you can use it)
• Having a cycle of length $n$ (Proof Problem 9)
• Being bipartite (Proof Problem 10)
• Being connected (Proof Problem 11)