Isomorphism of graphs Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What does it mean for two graphs to be isomorphic?
- There is a one-to-one correspondence between their vertices that preserves adjacency: adjacent in if and only if adjacent in .
- Name three necessary conditions for isomorphism.
- Same number of vertices, same number of edges, same degree sequence.
- Are the necessary conditions sufficient?
- No: and the triangular prism meet them all but are not isomorphic.
- What is a degree sequence?
- The degrees of all the vertices, listed in order of size.
- Why must isomorphic graphs have the same degree sequence?
- The isomorphism maps each vertex to a vertex with the same number of neighbours.
- How do you prove two graphs are isomorphic?
- Give a bijection between the vertices and show every edge maps to an edge, with equal numbers of edges.
- How do you prove two graphs are not isomorphic?
- Find a property an isomorphism must preserve (edges, degrees, triangles, bipartite) that differs.
- Must isomorphic graphs have the same vertex labels?
- No: only the structure must match.
- Can isomorphic graphs be drawn differently?
- Yes: drawings can differ completely.
- Does a triangle in one graph and none in the other prove non-isomorphism?
- Yes: isomorphisms preserve triangles.
- How can you use adjacency matrices to check isomorphism?
- Reorder the vertices of one graph; isomorphic graphs then have identical matrices.
- A vertex of degree 3 in maps to a vertex of what degree in ?
- Degree 3.