OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Independence and average degree: The density parameter used with independence number and ordinary clique exclusion

Average degree for finite simple graphs.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Independence bounds under clique exclusion compare the size of an independent set with the average degree of a finite simple graph. Write V(G)V(G) and E(G)E(G) for the vertex set and the set of unordered edges of a graph GG, respectively.

The Definition

Definition 1. Let GG be a finite simple graph. The average degree d(G)d(G) of GG is the real number given by (1) when V(G)V(G) is nonempty, and is 00 when V(G)V(G) is empty. d(G)=2|E(G)||V(G)|.d(G)=\frac{2|E(G)|}{|V(G)|}.(1)✦

In the paper, an independent set II of a finite simple graph GG is a set of pairwise nonadjacent vertices of GG and the independence number α(G)\alpha(G) of GG is the maximum size of such a set; for n=|V(G)|>0n=|V(G)|>0, d(G)=2|E(G)|/nd(G)=2|E(G)|/n; and, for a natural number rr, GG is KrK_r-free if it contains no rr pairwise adjacent vertices, with ordinary subgraph exclusion.

What Is Checked

The average degree is defined for finite simple graphs.