diff --git a/commit-graph.c b/commit-graph.c
index ca84423042..0d5474852c 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -418,6 +418,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,
 	if (graph_signature != GRAPH_SIGNATURE) {
 		error(_("commit-graph signature %X does not match signature %X"),
 		      graph_signature, GRAPH_SIGNATURE);
+		error(_("try running: git commit-graph clear"));
 		return NULL;
 	}
 
@@ -425,6 +426,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,
 	if (graph_version != GRAPH_VERSION) {
 		error(_("commit-graph version %X does not match version %X"),
 		      graph_version, GRAPH_VERSION);
+		error(_("try running: git commit-graph clear"));
 		return NULL;
 	}
 
@@ -432,6 +434,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,
 	if (hash_version != oid_version(the_hash_algo)) {
 		error(_("commit-graph hash version %X does not match version %X"),
 		      hash_version, oid_version(the_hash_algo));
+		error(_("try running: git commit-graph clear"));
 		return NULL;
 	}
 
@@ -447,6 +450,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,
 			 GRAPH_FANOUT_SIZE + the_hash_algo->rawsz) {
 		error(_("commit-graph file is too small to hold %u chunks"),
 		      graph->num_chunks);
+		error(_("try running: git commit-graph clear"));
 		free(graph);
 		return NULL;
 	}
@@ -459,14 +463,17 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,
 
 	if (read_chunk(cf, GRAPH_CHUNKID_OIDFANOUT, graph_read_oid_fanout, graph)) {
 		error(_("commit-graph required OID fanout chunk missing or corrupted"));
+		error(_("try running: git commit-graph clear"));
 		goto free_and_return;
 	}
 	if (read_chunk(cf, GRAPH_CHUNKID_OIDLOOKUP, graph_read_oid_lookup, graph)) {
 		error(_("commit-graph required OID lookup chunk missing or corrupted"));
+		error(_("try running: git commit-graph clear"));
 		goto free_and_return;
 	}
 	if (read_chunk(cf, GRAPH_CHUNKID_DATA, graph_read_commit_data, graph)) {
 		error(_("commit-graph required commit data chunk missing or corrupted"));
+		error(_("try running: git commit-graph clear"));
 		goto free_and_return;
 	}
 
@@ -860,7 +867,8 @@ static void load_oid_from_graph(struct commit_graph *g,
 		BUG("NULL commit-graph");
 
 	if (pos >= g->num_commits + g->num_commits_in_base)
-		die(_("invalid commit position. commit-graph is likely corrupt"));
+		die(_("invalid commit position. The commit-graph is likely corrupt,\n"
+		      "try running:\n\tgit commit-graph clear"));
 
 	lex_index = pos - g->num_commits_in_base;
 
@@ -876,7 +884,8 @@ static struct commit_list **insert_parent_or_die(struct repository *r,
 	struct object_id oid;
 
 	if (pos >= g->num_commits + g->num_commits_in_base)
-		die("invalid parent position %"PRIu32, pos);
+		die("invalid parent position %"PRIu32". The commit-graph is likely corrupt,\n"
+		    "try running:\n\tgit commit-graph clear", pos);
 
 	load_oid_from_graph(g, pos, &oid);
 	c = lookup_commit(r, &oid);
@@ -897,7 +906,8 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
 		g = g->base_graph;
 
 	if (pos >= g->num_commits + g->num_commits_in_base)
-		die(_("invalid commit position. commit-graph is likely corrupt"));
+		die(_("invalid commit position. commit-graph is likely corrupt,\n"
+		      "try running:\n\tgit commit-graph clear"));
 
 	lex_index = pos - g->num_commits_in_base;
 	commit_data = g->chunk_commit_data + st_mult(GRAPH_DATA_WIDTH, lex_index);
diff --git a/commit-reach.c b/commit-reach.c
index ecc913fc99..16765ce39b 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -81,7 +81,9 @@ static struct commit_list *paint_down_to_common(struct repository *r,
 		timestamp_t generation = commit_graph_generation(commit);
 
 		if (min_generation && generation > last_gen)
-			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
+			BUG("bad generation skip %"PRItime" > %"PRItime" at %s\n"
+			    "The commit graph is likely corrupt, try running:\n"
+			    "\tgit commit-graph clear",
 			    generation, last_gen,
 			    oid_to_hex(&commit->object.oid));
 		last_gen = generation;
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 35354bddcb..f4553b1916 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -843,6 +843,7 @@ test_expect_success 'reader notices too-small oid fanout chunk' '
 	cat >expect.err <<-\EOF &&
 	error: commit-graph oid fanout chunk is wrong size
 	error: commit-graph required OID fanout chunk missing or corrupted
+	error: try running: git commit-graph clear
 	EOF
 	test_cmp expect.err err
 '
@@ -852,6 +853,7 @@ test_expect_success 'reader notices fanout/lookup table mismatch' '
 	cat >expect.err <<-\EOF &&
 	error: commit-graph OID lookup chunk is the wrong size
 	error: commit-graph required OID lookup chunk missing or corrupted
+	error: try running: git commit-graph clear
 	EOF
 	test_cmp expect.err err
 '
@@ -868,6 +870,7 @@ test_expect_success 'reader notices out-of-bounds fanout' '
 	cat >expect.err <<-\EOF &&
 	error: commit-graph fanout values out of order
 	error: commit-graph required OID fanout chunk missing or corrupted
+	error: try running: git commit-graph clear
 	EOF
 	test_cmp expect.err err
 '
@@ -877,6 +880,7 @@ test_expect_success 'reader notices too-small commit data chunk' '
 	cat >expect.err <<-\EOF &&
 	error: commit-graph commit data chunk is wrong size
 	error: commit-graph required commit data chunk missing or corrupted
+	error: try running: git commit-graph clear
 	EOF
 	test_cmp expect.err err
 '
