diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c
index 153a92fd3ea..00990b33859 100644
--- a/src/backend/utils/adt/ruleutils.c
+++ b/src/backend/utils/adt/ruleutils.c
@@ -330,6 +330,13 @@ typedef struct
 typedef void (*rsv_callback) (Node *node, deparse_context *context,
 							  void *callback_arg);
 
+/* Used by make_propgraphdef_labels to sort labels by name */
+typedef struct
+{
+	const char *labelname;
+	Oid			ellabelid;		/* pg_propgraph_element_label OID */
+} PropGraphLabelEntry;
+
 
 /* ----------
  * Global data
@@ -368,6 +375,7 @@ static char *pg_get_indexdef_worker(Oid indexrelid, int colno,
 									int prettyFlags, bool missing_ok);
 static void make_propgraphdef_elements(StringInfo buf, Oid pgrelid, char pgekind);
 static void make_propgraphdef_labels(StringInfo buf, Oid elid, const char *elalias, Oid elrelid);
+static int	labelentry_name_cmp(const void *a, const void *b);
 static void make_propgraphdef_properties(StringInfo buf, Oid ellabelid, Oid elrelid);
 static char *pg_get_statisticsobj_worker(Oid statextid, bool columns_only,
 										 bool missing_ok);
@@ -1776,14 +1784,28 @@ make_propgraphdef_elements(StringInfo buf, Oid pgrelid, char pgekind)
  * Generates label and properties list.  Pass in the element OID, the element
  * alias, and the graph relation OID.  Result is appended to buf.
  */
+/*
+ * Comparison function for qsort: sort label entries by label name.
+ */
+static int
+labelentry_name_cmp(const void *a, const void *b)
+{
+	const PropGraphLabelEntry *la = (const PropGraphLabelEntry *) a;
+	const PropGraphLabelEntry *lb = (const PropGraphLabelEntry *) b;
+
+	return strcmp(la->labelname, lb->labelname);
+}
+
 static void
 make_propgraphdef_labels(StringInfo buf, Oid elid, const char *elalias, Oid elrelid)
 {
 	Relation	pglrel;
 	ScanKeyData scankey[1];
 	SysScanDesc scan;
-	int			count;
 	HeapTuple	tup;
+	PropGraphLabelEntry *labels;
+	int			nlabels = 0;
+	int			maxlabels = 8;
 
 	pglrel = table_open(PropgraphElementLabelRelationId, AccessShareLock);
 
@@ -1792,38 +1814,48 @@ make_propgraphdef_labels(StringInfo buf, Oid elid, const char *elalias, Oid elre
 				BTEqualStrategyNumber, F_OIDEQ,
 				ObjectIdGetDatum(elid));
 
-	count = 0;
-	scan = systable_beginscan(pglrel, PropgraphElementLabelElementLabelIndexId, true, NULL, 1, scankey);
-	while ((tup = systable_getnext(scan)))
-	{
-		count++;
-	}
-	systable_endscan(scan);
+	/*
+	 * Collect all labels first so we can sort them by name, ensuring a
+	 * deterministic output order regardless of catalog OID assignment.
+	 */
+	labels = palloc(maxlabels * sizeof(PropGraphLabelEntry));
 
 	scan = systable_beginscan(pglrel, PropgraphElementLabelElementLabelIndexId, true, NULL, 1, scankey);
-
 	while ((tup = systable_getnext(scan)))
 	{
 		Form_pg_propgraph_element_label pgelform = (Form_pg_propgraph_element_label) GETSTRUCT(tup);
-		const char *labelname;
 
-		labelname = get_propgraph_label_name(pgelform->pgellabelid);
+		if (nlabels >= maxlabels)
+		{
+			maxlabels *= 2;
+			labels = repalloc(labels, maxlabels * sizeof(PropGraphLabelEntry));
+		}
 
-		if (strcmp(labelname, elalias) == 0)
+		labels[nlabels].labelname = pstrdup(get_propgraph_label_name(pgelform->pgellabelid));
+		labels[nlabels].ellabelid = pgelform->oid;
+		nlabels++;
+	}
+	systable_endscan(scan);
+
+	table_close(pglrel, AccessShareLock);
+
+	qsort(labels, nlabels, sizeof(PropGraphLabelEntry), labelentry_name_cmp);
+
+	for (int i = 0; i < nlabels; i++)
+	{
+		if (strcmp(labels[i].labelname, elalias) == 0)
 		{
 			/* If the default label is the only label, don't print anything. */
-			if (count != 1)
+			if (nlabels != 1)
 				appendStringInfo(buf, " DEFAULT LABEL");
 		}
 		else
-			appendStringInfo(buf, " LABEL %s", quote_identifier(labelname));
+			appendStringInfo(buf, " LABEL %s", quote_identifier(labels[i].labelname));
 
-		make_propgraphdef_properties(buf, pgelform->oid, elrelid);
+		make_propgraphdef_properties(buf, labels[i].ellabelid, elrelid);
 	}
 
-	systable_endscan(scan);
-
-	table_close(pglrel, AccessShareLock);
+	pfree(labels);
 }
 
 /*
diff --git a/src/bin/pg_dump/pg_dump.c b/src/bin/pg_dump/pg_dump.c
index b41a3ae3db4..23af95027e6 100644
--- a/src/bin/pg_dump/pg_dump.c
+++ b/src/bin/pg_dump/pg_dump.c
@@ -20473,11 +20473,12 @@ getDependencies(Archive *fout)
 	 * Translate dependencies of pg_propgraph_element entries into
 	 * dependencies of their parent pg_class entry.
 	 */
-	appendPQExpBufferStr(query, "UNION ALL\n"
-						 "SELECT 'pg_class'::regclass AS classid, pgepgid AS objid, refclassid, refobjid, deptype "
-						 "FROM pg_depend d, pg_propgraph_element pge "
-						 "WHERE deptype NOT IN ('p', 'e', 'i') AND "
-						 "classid = 'pg_propgraph_element'::regclass AND objid = pge.oid\n");
+	if (fout->remoteVersion >= 190000)
+		appendPQExpBufferStr(query, "UNION ALL\n"
+							 "SELECT 'pg_class'::regclass AS classid, pgepgid AS objid, refclassid, refobjid, deptype "
+							 "FROM pg_depend d, pg_propgraph_element pge "
+							 "WHERE deptype NOT IN ('p', 'e', 'i') AND "
+							 "classid = 'pg_propgraph_element'::regclass AND objid = pge.oid\n");
 
 	/* Sort the output for efficiency below */
 	appendPQExpBufferStr(query, "ORDER BY 1,2");