diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 9a297b2..4bf7fb3 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -919,6 +919,10 @@
             scopedMethodsForLiveTypes.computeIfAbsent(
                 holder.superType, ignore -> new ScopedDexMethodSet());
         seen.setParent(seenForSuper);
+        DexClass holderSuper = appView.definitionFor(holder.superType);
+        if (holderSuper != null && holderSuper.isProgramClass()) {
+          registerType(holder.superType, KeepReason.reachableFromLiveType(type));
+        }
         markTypeAsLive(holder.superType, seenForSuper);
         if (holder.isNotProgramClass()) {
           // Library classes may only extend other implement library classes.
diff --git a/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptSubclassKeepsSuperTest.java b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptSubclassKeepsSuperTest.java
index 6bc7cb5..72bd54e 100644
--- a/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptSubclassKeepsSuperTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptSubclassKeepsSuperTest.java
@@ -11,7 +11,6 @@
 import com.android.tools.r8.TestParametersBuilder;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.origin.Origin;
-import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.Reference;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.graphinspector.GraphInspector;
@@ -46,7 +45,6 @@
             .enableMergeAnnotations()
             .addProgramClasses(CLASS, Foo.class, Bar.class)
             .addKeepMainRule(CLASS)
-            .noMinification()
             .run(parameters.getRuntime(), CLASS)
             .assertSuccessWithOutput(EXPECTED)
             .graphInspector();
@@ -58,10 +56,8 @@
     QueryNode fooClass = inspector.clazz(Reference.classFromClass(Foo.class));
     fooClass.assertPresent();
 
-    ClassReference barClassRef = Reference.classFromClass(Bar.class);
-    QueryNode barClass = inspector.clazz(barClassRef);
-    // TODO(b/135474075): No edge is reported for the super class!
-    barClass.assertAbsent();
+    QueryNode barClass = inspector.clazz(Reference.classFromClass(Bar.class));
+    barClass.assertPresent().assertKeptBy(fooClass);
   }
 
   @NeverMerge