Graph Isomorphism and Homomorphism | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 9.4 Free with a free account

Graph Isomorphism and Homomorphism

Discrete Mathematics · Chapter 9: Graph Theory: Foundations and Euler PathsSection 9.4 · lesson 62 of 879 min · free with a free account

← Types of Graphs and Their PropertiesNext lesson: Euler Paths and Circuits →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

When 2 graphs are the same - and when one merely maps into another.

  • Define and verify a graph isomorphism
  • Use invariants to rule isomorphism out
  • Define a homomorphism and contrast it
  • See graph coloring as a homomorphism

Transcript

Everything said in the video, section by section (1,286 words). Read along, or search it.

Graph Theory: Foundations and Euler Paths

Graph Isomorphism and Homomorphism

This section asks when two graphs are really the same, and when one graph merely maps into another. The first is isomorphism, a perfect match up to relabeling. The second is homomorphism, a strictly weaker idea that turns out to be what graph coloring really is.

The Opening Problem

The Same Molecule, Numbered Differently

A chemistry informatics team keeps a database of molecular structures, each stored as a graph. Atoms are vertices, and bonds are edges. When a new compound is submitted, the system must check whether it's already there under a different atom numbering. The same molecule, indexed differently, shouldn't be stored twice. That's exactly the question of whether two graphs are isomorphic. Structurally identical, differing only in how their vertices are labeled. The same question arises in checking whether a chip layout implements a reference schematic. A closely related but weaker question is whether one graph's structure can be mapped into another, without matching it exactly. That's a homomorphism. It underlies graph coloring and constraint satisfaction problems.

Definition 9.4.1

Graph Isomorphism

This section works with simple, undirected graphs. Two graphs can look completely different when drawn, and still have the identical structure of connections. Graphs G and H are isomorphic if there's a bijection from G's vertices to H's. That's a function that's one-to-one and onto, pairing the vertices up with none left over. And it must satisfy this. u v is an edge of G, if and only if f of u, f of v is an edge of H. That if and only if does two jobs. Every edge of G must land on an edge of H, so nothing gets disconnected. And every edge of H must come from an edge of G, so nothing gets newly connected. An isomorphism is a relabeling, not a redesign.

Worked Example 9.4.1

2 Drawings of a 4-Cycle

Here's an example. G has vertices one through four, with edges forming a four-cycle. H has vertices w, x, y, and z, with edges w y, y x, x z, and z w. Propose f sending one to w, two to y, three to x, and four to z. Each of G's vertices goes to a different vertex of H, and all four of H's vertices are hit. So f is a bijection. Now the forward direction. One-two becomes w y. Two-three becomes y x. Three-four becomes x z. And four-one becomes z w. All four are edges of H. And those four images are all of H's edges, each hit once. So nothing in H lacks a partner. So f is an isomorphism. Both graphs are four-cycles. H is just G redrawn as a diamond, with new names.

Theorem 9.4.1

Invariants: Necessary Conditions

Exhibiting a bijection proves two graphs are isomorphic. Proving they're not is often easier. Find a property that any isomorphism must preserve, and show the graphs disagree on it. Such a property is called an invariant. It's computed from structure alone, not from labels or a drawing. If two graphs are isomorphic, they have the same number of vertices, the same number of edges, and identical degree sequences. Here's why the degrees match. u is a neighbor of v exactly when f of u is a neighbor of f of v. And since f is one-to-one, it pairs up v's neighbors with f of v's neighbors. Two finite sets in one-to-one correspondence have the same size. So the degrees are equal, vertex by vertex.

Worked Example 9.4.3

Matching Invariants Aren't Enough

But these invariants are necessary, not sufficient. Here are two graphs, P and Q. Both have six vertices and six edges. P is a single six-cycle, and Q is two separate triangles. In both, every vertex has degree two. So every invariant from the theorem agrees. But look at connectivity, another invariant. An isomorphism is a relabeling, so it can't merge or split connected components. P is connected, a single piece. Q has two components, with no path from one triangle to the other. So no isomorphism can exist. Cheap invariants make a useful first screen. But a full test needs finer invariants, or an actual search for a bijection.

Definition 9.4.2

Graph Homomorphism

Isomorphism requires a perfect match in both directions. A homomorphism is strictly weaker. A homomorphism from G to H is any function on the vertices with one property. If u v is an edge of G, then f of u, f of v is an edge of H. Only the forward direction. f needn't be one-to-one, so two vertices of G may share a target. It needn't be onto, so some of H may be missed. And non-edges of G may land on edges of H. Every isomorphism is automatically a homomorphism. The if and only if contains the forward implication. But the converse fails. Plenty of homomorphisms exist between graphs of very different sizes, where no isomorphism could, since the vertex counts don't even match.

Table 9.4.1

Isomorphism Versus Homomorphism

This table contrasts the two. An isomorphism must be a bijection, and it preserves edges in both directions. A homomorphism can be any function, and only preserves edges forward. An isomorphism forces equal vertex and edge counts. A homomorphism constrains neither, so H may be much smaller than G. Isomorphism is symmetric, because it can be inverted. A homomorphism generally can't be. Isomorphism tests whether two graphs are the same structure, like duplicate molecules or equivalent layouts. Homomorphism tests whether a structure can be compressed or colored consistently, against a fixed target.

Worked Example 9.4.4

Coloring Is a Homomorphism Into K(k)

A proper k-coloring assigns one of k colors to each vertex, so that no edge joins two vertices of the same color. It's used in scheduling and register allocation, covered later in the course. The claim is that a proper k-coloring exists exactly when there's a homomorphism from G into the complete graph on k vertices. First direction. Treat the k colors as the vertices of the complete graph. Adjacent vertices get different colors. And every two different vertices of the complete graph are joined. So edges map to edges. Second direction. Given a homomorphism, color each vertex by its image. An edge maps to an edge. And the complete graph has no loops, so the two ends get different images, which means different colors. This could never be phrased with isomorphism. G usually has far more vertices than k. The whole point is that many vertices can share one color.

Why It Matters in Practice

2 Problems, 2 Levels of Difficulty

The distinction matters computationally. Deciding whether a homomorphism exists into a fixed target is hard in general. Deciding whether a three-coloring exists, which is a homomorphism into K three, is N P complete. No algorithm is known that solves every instance quickly, and most researchers believe none exists. Isomorphism sits in a curious middle ground. László Babai announced a quasi-polynomial time algorithm for it in twenty fifteen, a big improvement over earlier methods. But its exact classification hasn't been settled. It hasn't been shown solvable in polynomial time, or shown N P complete. In practice, real isomorphism checkers, like those in chemistry databases and circuit tools, screen with cheap invariants first. That quickly rejects non-isomorphic pairs, before any search for a bijection.

Takeaways

Relabel, or Map Into

To summarize. Two graphs are isomorphic exactly when a bijection between their vertices preserves adjacency in both directions. Vertex count, edge count, and degree sequence are necessary invariants. A mismatch rules isomorphism out. But matching them isn't enough. A homomorphism only requires edges to map to edges, forward. And a proper k-coloring is exactly a homomorphism into the complete graph on k vertices. Here's something to think about. A classmate checks two graphs and finds matching vertex counts, edge counts, degree sequences, and numbers of components. They conclude the graphs must be isomorphic. Is that justified, or does it confuse a necessary condition with a sufficient one? If no finite checklist of invariants guarantees isomorphism, what would actually prove it with certainty? And what would prove they're not isomorphic, when every invariant agrees?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Graph Isomorphism and Homomorphism

What does it mean for two graphs to be isomorphic, and how do you verify it?
Two graphs G and H are isomorphic if there is a bijection f from the vertices of G to those of H such that uv is an edge of G if and only if f(u)f(v) is an edge of H. To verify one, check that f is one-to-one and onto, then check that edges map to edges in both directions.
How can you show two graphs are not isomorphic?
Find an invariant, a property computed from structure alone, on which the graphs disagree. Isomorphic graphs must have the same number of vertices, the same number of edges, and the same degree sequence. They must also have the same number of connected components. A single mismatch rules isomorphism out.
If two graphs have the same number of vertices, edges, and degree sequence, must they be isomorphic?
No, matching these invariants is necessary but not sufficient. A six-cycle and two disjoint triangles both have 6 vertices, 6 edges, and every vertex of degree 2. The six-cycle is connected, though, and the triangles form two components. No isomorphism can merge or split components, so the graphs are not isomorphic.
How is a graph homomorphism different from an isomorphism, and how does it relate to coloring?
A homomorphism is any vertex function where each edge uv of G maps to an edge f(u)f(v) of H. It need not be one-to-one, onto, or preserve non-edges, so it is weaker than an isomorphism. A proper k-coloring of G is exactly a homomorphism from G into the complete graph K_k.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →