Skip to content

feat(SimpleGraph): card of common neighbors equals card of triangles containing edge#37109

Open
zeekmartin wants to merge 6 commits intoleanprover-community:masterfrom
zeekmartin:feat/SimpleGraph-commonNeighbors-triangle
Open

feat(SimpleGraph): card of common neighbors equals card of triangles containing edge#37109
zeekmartin wants to merge 6 commits intoleanprover-community:masterfrom
zeekmartin:feat/SimpleGraph-commonNeighbors-triangle

Conversation

@zeekmartin
Copy link
Copy Markdown

@zeekmartin zeekmartin commented Mar 24, 2026 •
edited
Loading

Adds SimpleGraph.card_commonNeighbors_eq_card_triangles_containing_edge
to Mathlib/Combinatorics/SimpleGraph/Clique.lean.

For adjacent vertices u v in a finite simple graph, establishes the bijection
between common neighbors and 3-cliques containing the edge {u, v}:

theorem card_commonNeighbors_eq_card_triangles_containing_edge
    {u v : α} (huv : G.Adj u v) :
    (G.commonNeighbors u v).toFinset.card =
      ((G.cliqueFinset 3).filter fun s => {u, v} ⊆ s).card

This connects commonNeighbors (defined in Basic.lean) with cliqueFinset —
a gap not previously covered in Clique.lean.

AI disclosure: Claude (Anthropic) was used as an assistant during the development of this proof. It helped with the initial proof structure and tactic suggestions. The proof was reviewed and validated step by step by the author, who can vouch for all the content. The mathematical idea originates from the author's prior Lean 4 work on spectral graph theory (github.com/zeekmartin/topostability-lean4).

Open in Gitpod

@zeekmartin
feat(SimpleGraph): card of common neighbors equals card of triangles …
9213a81 
…containing edge

For adjacent vertices u v, prove that the number of common neighbors
equals the number of 3-cliques containing {u, v}.
@github-actions github-actions bot added the new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! label Mar 24, 2026
@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 24, 2026

Welcome new contributor!

Thank you for contributing to Mathlib! If you haven't done so already, please review our contribution guidelines, as well as the style guide and naming conventions. In particular, we kindly remind contributors that we have guidelines regarding the use of AI when making pull requests.

We use a review queue to manage reviews. If your PR does not appear there, it is probably because it is not successfully building (i.e., it doesn't have a green checkmark), has the awaiting-author tag, or another reason described in the Lifecycle of a PR. The review dashboard has a dedicated webpage which shows whether your PR is on the review queue, and (if not), why.

If you haven't already done so, please come to https://leanprover.zulipchat.com/, introduce yourself, and mention your new PR.

Thank you again for joining our community.

@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 24, 2026 •
edited
Loading

PR summary 0587621189

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference

Declarations diff

+ card_commonNeighbors_eq_card_triangles_containing_edge

You can run this locally as follows 
## summary with just the declaration names:
./scripts/pr_summary/declarations_diff.sh <optional_commit>

## more verbose report:
./scripts/pr_summary/declarations_diff.sh long <optional_commit>

The doc-module for scripts/pr_summary/declarations_diff.sh contains some details about this script.

No changes to technical debt.

You can run this locally as

./scripts/reporting/technical-debt-metrics.sh pr_summary
  • The relative value is the weighted sum of the differences with weight given by the inverse of the current value of the statistic.
  • The absolute value is the relative value divided by the total sum of the inverses of the current values (i.e. the weighted average of the differences).

@github-actions github-actions bot added the t-combinatorics Combinatorics label Mar 24, 2026
@zeekmartin
Copy link
Copy Markdown
Author

zeekmartin commented Mar 24, 2026

AI disclosure: Claude (Anthropic) was used as an assistant during the development of this proof. Specifically, it helped with the initial proof structure and tactic suggestions. The proof was reviewed, understood, and validated step by step by the author, who can vouch for all the content.

The mathematical idea (bijection between common neighbors and triangles containing an edge) originates from the author's prior Lean 4 work on spectral graph theory (github.com/zeekmartin/topostability-lean4).

@RemyDegenne RemyDegenne added the LLM-generated PRs with substantial input from LLMs - review accordingly label Mar 24, 2026
SnirBroshi
SnirBroshi reviewed Mar 24, 2026
View reviewed changes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer

@SnirBroshi SnirBroshi SnirBroshi left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

LLM-generated PRs with substantial input from LLMs - review accordingly new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! t-combinatorics Combinatorics

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@zeekmartin @SnirBroshi @RemyDegenne