Graphs · step 6 of 14

Adjacency matrices & isomorphism

The adjacency matrix A has Aᵢⱼ = 1 exactly when vertices i and j are joined; for an undirected graph it is symmetric with zero diagonal. Entry (i,j) of Aᵏ counts the walks of length k between those vertices, which is a genuinely useful computational fact. Two graphs are isomorphic when a relabelling makes their matrices identical — proved by exhibiting the bijection, refuted by an invariant.

Practise adjacency matrices & isomorphism free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Write A with a stated vertex orderRows and columns must use the same order, and the order should be recorded with the matrix.
Count walks with powers(Aᵏ)ᵢⱼ is the number of walks of length k from i to j. The trace of A³ is six times the number of triangles.
Compare invariants for isomorphismVertex count, edge count, degree sequence, number of triangles, connectivity, eigenvalues. A mismatch settles it.
Construct the bijection for a positive answerMap high-degree vertices to high-degree vertices, then verify every edge maps to an edge and every non-edge to a non-edge.

Worked example

Two graphs both have 5 vertices, 6 edges and degree sequence (2,2,2,3,3). Is that enough to conclude they are isomorphic?

These invariants match, which is necessary but not sufficient.
Distinguish further: count triangles via the trace of A³ divided by 6.
One graph may contain a triangle while the other is triangle-free.
If every invariant matches, attempt an explicit bijection.

Answer. No — matching degree sequences do not imply isomorphism. Triangle counts, cycle lengths or an explicit bijection are needed to decide.

Where marks get dropped

These are the specific errors that cost credit on adjacency matrices & isomorphism questions — QED's rubric penalises each of them separately.

Treating a matching degree sequence as proof of isomorphism. It is only a necessary condition.
Comparing adjacency matrices under one fixed labelling. Isomorphic graphs usually have different matrices until relabelled.
Forgetting that walks counted by Aᵏ may repeat vertices — they are walks, not paths.

Practise this until it is automatic

Unlimited fresh questions

QED generates new adjacency matrices & isomorphism problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Adjacency matrices & isomorphism — frequently asked questions

How do I count triangles from A?

trace(A³)/6. Each triangle is counted once per starting vertex (3) and per direction (2).

Are cospectral graphs isomorphic?

Not necessarily. Non-isomorphic graphs can share the same adjacency eigenvalues, so the spectrum is a strong but incomplete invariant.

How hard is graph isomorphism?

No polynomial algorithm is known, but it is not known to be NP-complete either. Babai’s quasi-polynomial algorithm is the current best.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make adjacency matrices & isomorphism exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →