7.02j, 7.02k - Isomorphic graphs and digraphs

7.02j, 7.02k - Isomorphic graphs and digraphs

Decide when different drawings encode the same connections, then describe connections that have a direction. In 7.02j7.02j you will construct an isomorphism and use structural differences to disprove one; in 7.02k7.02k you will work with digraphs, indegrees and outdegrees.

What an isomorphism preserves

One diagram is drawn as a hexagon; another as two triangles with links between them. Does a change of drawing change the graph, or only its appearance? Counting dots and lines is a start, but it cannot always answer the question.

You already know

A graph records which vertices are adjacent. A degree sequence lists the vertex degrees, usually in decreasing order. A bipartite graph has no odd cycle.

An exact correspondence must match connections, not positions. If a vertex represents a busy junction with three neighbours, its replacement must also have three neighbours, with the same pattern of connections among them.

Isomorphic graphs

Two graphs are isomorphic if there is a one-to-one correspondence between their vertex sets that preserves adjacency, including the number of arcs between each corresponding pair and any loops. The graphs have the same connection structure after relabelling. Graphs that admit no such correspondence are non-isomorphic. These definitions are not supplied in the formula booklet.

An isomorphism preserves the numbers of vertices and arcs, vertex degrees and hence the degree sequence. It also preserves connectedness and the numbers of cycles of each length. These are invariants: quantities or properties that cannot change under a relabelling. Two unequal invariants disprove isomorphism. Matching invariants merely keep it possible. These invariant properties and their use are not supplied in the formula booklet.

For a concrete warning, both a six-cycle and two separate triangles have six degree-two vertices and six arcs. One is connected and the other is not, so no relabelling can make them the same graph.

Key idea

A matching degree sequence is necessary for isomorphism, but is not sufficient. To prove isomorphism, give a correspondence that preserves every connection.

The distinction is the same logical one as a useful screening test: passing one necessary check does not settle the whole problem.

Constructing an isomorphism

Begin with distinctive vertices: a unique degree-one vertex, a unique high-degree vertex, or a vertex in a distinctive cycle. Match their neighbours next. When some vertices have the same degree, their connections to already matched vertices can distinguish them.

[DIAGRAM: asset_name: An explicit relabelling; asset_slug: h245_7_02_isomorphism; caption: The correspondence A to 1, B to 3, C to 2, D to 4 preserves every arc; description: Left graph is triangle ABC with pendant edge CD; right graph has edges 12 23 31 24 in a different layout. A mapping table shows A maps to 1, B to 3, C to 2, D to 4. Both degree-three vertices and both degree-one vertices have matching accent colours.]
The correspondence A to 1, B to 3, C to 2, D to 4 preserves every arc

Worked example 1: matching distinctive vertices

Question. Graph GG has arcs AB,BC,CA,CDAB, BC, CA, CD. Graph HH has arcs 12,23,31,2412, 23, 31, 24. Construct an isomorphism from GG to HH.

Plan. Match the unique degree-three and degree-one vertices, then check the triangle.

C↦2unique degree-three verticesD↦4unique degree-one verticesA↦1,B↦3match the remaining triangle verticesAB,BC,CA,CD↦13,32,21,24check every arc\begin{aligned} C&\mapsto2 && \text{unique degree-three vertices}\\ D&\mapsto4 && \text{unique degree-one vertices}\\ A&\mapsto1,\quad B\mapsto3 && \text{match the remaining triangle vertices}\\ AB,BC,CA,CD&\mapsto13,32,21,24 && \text{check every arc} \end{aligned}

Why this step? Distinctive degrees fix two matches immediately; the final arc check establishes the entire correspondence.

Answer. A↦1, B↦3, C↦2, D↦4A\mapsto1,\ B\mapsto3,\ C\mapsto2,\ D\mapsto4 is an isomorphism.

Check. The four image arcs are exactly HH's four arcs, and every vertex is used once.

The second example changes one feature: the pendant connection is lengthened by one vertex. Match its distance from the triangle as well as its degree.

Worked example 2: matching a longer branch

Question. Graph GG has arcs AB,BC,CA,CD,DEAB, BC, CA, CD, DE. Graph HH has arcs 35,51,13,14,4235, 51, 13, 14, 42. Construct an isomorphism.

Plan. Match the degree-three vertex and its branch first, then match the two other triangle vertices.

C↦1unique degree threeD↦4,E↦2follow the branch to degree oneA↦3,B↦5complete the triangleAB,BC,CA,CD,DE↦35,51,13,14,42check every arc\begin{aligned} C&\mapsto1 && \text{unique degree three}\\ D&\mapsto4,\quad E\mapsto2 && \text{follow the branch to degree one}\\ A&\mapsto3,\quad B\mapsto5 && \text{complete the triangle}\\ AB,BC,CA,CD,DE&\mapsto35,51,13,14,42 && \text{check every arc} \end{aligned}

Why this step? The degree-two branch vertex DD must map to 44, rather than to either degree-two triangle vertex.

Answer. The mapping is A↦3, B↦5, C↦1, D↦4, E↦2A\mapsto3,\ B\mapsto5,\ C\mapsto1,\ D\mapsto4,\ E\mapsto2.

Check. It is a bijection and its image arc list equals the complete list for HH.

A clearly labelled diagram or an explicit mapping can prove the correspondence. Saying “the graphs look the same when stretched” leaves the matching unstated.

Exam tip

Give the direction of your mapping and one image for every vertex. A degree sequence alone cannot earn the conclusion that the graphs are isomorphic.

Try a new labelling of the same branch structure.

Disproving an isomorphism

A structural difference is enough to prove that no mapping works. Use an invariant that actually differs; testing a few unsuccessful labellings does not rule out every possible correspondence.

[DIAGRAM: asset_name: Equal degrees, different cycles; asset_slug: h245_7_02_nonisomorphic; caption: Both graphs have six degree-three vertices, but only the triangular prism contains triangles; description: Left panel shows K3,3 with two colour classes of three vertices. Right panel shows a triangular prism with triangles ABC and DEF and matching edges AD BE CF. Both panels state degree sequence 3 3 3 3 3 3; the right triangles are accented.]
Both graphs have six degree-three vertices, but only the triangular prism contains triangles

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account