Isomorphism of graphs

Isomorphism of graphs Flashcards

Spec DA7 · AQA A-Level Further Maths: 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: u,vu,v adjacent in GG if and only if f(u),f(v)f(u),f(v) adjacent in HH.
Name three necessary conditions for isomorphism.
Same number of vertices, same number of edges, same degree sequence.
Are the necessary conditions sufficient?
No: K3,3K_{3,3} 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 GG maps to a vertex of what degree in HH?
Degree 3.

Flashcards