card_commonNeighbors_le_degree_right

Mathlib.Combinatorics.SimpleGraph.Finite

URI: https://scilib.ai/kg/mathlib#SimpleGraph.card_commonNeighbors_le_degree_right

← MathLib Explorer

English

Similarly, for all v,w in G, |commonNeighbors(v,w)| ≤ deg_G(w).

Русский

Аналогично, для любых v,w графа G: |commonNeighbors(v,w)| ≤ deg_G(w).

LaTeX

$$$\\#(G.commonNeighbors\\) (v,w) \\leq \\deg_G(w)$$$

Lean4

theorem card_commonNeighbors_le_degree_right [DecidableRel G.Adj] (v w : V) :
    Fintype.card (G.commonNeighbors v w) ≤ G.degree w := by
  simp_rw [commonNeighbors_symm _ v w, card_commonNeighbors_le_degree_left]

Похожие утверждения

Научная платформа российской исследовательской школы.

Разделы

MathLib Explorer
Graph RAG
Лаборатория
Блог
О проекте
Команда

Аффилиация

Вычислительный центр им. А. А. Дороницына при ФИЦ «Информатика и Управление» РАН frccsc.ru