Finite simple undirected graphs

Mathematical statement

A finite simple undirected graph G=(V,E) consists of a finite vertex set V and an edge set E of two-element subsets of V. There are no loops or multiple edges. N(v)={u∈V:{u,v}∈E}, deg(v)=|N(v)|, and the sum of all vertex degrees is 2|E|.

Representative formula (exact TeX)

G(V,E)

Assumptions

• V is finite with distinct vertex labels, and every edge has two distinct endpoints in V.
• An undirected edge ignores endpoint order. Neighbor and degree questions specify v∈V; the empty graph is permitted.

Symbol scope

• G — finite simple undirected graph
• V — vertex set
• E — unordered edge set

Intuition, definition, and misconceptions

Treat {u,v} and {v,u} as the same undirected edge. Normalize duplicate entries in a set representation; endpoint ordering and repeated list items do not create a new graph.

A vertex degree is its number of distinct neighbors; an isolated vertex has degree zero. In this simple-graph setting, every edge contributes twice to the total degree sum, giving the handshaking identity.

A graph in graph theory is distinct from a coordinate graph of a function, and a drawing does not determine adjacency. Directed graphs, multigraphs, loop-counting conventions, connectivity, and tree classification are outside this pulse.

Common errors include counting both endpoint orders as two undirected edges, or reading a crossing of drawn lines as an additional vertex.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Set — Vertices and undirected edges form sets; duplicate representations add no edge.
• Binary relations and set projections — Adjacency is a finite symmetric relation without self-loops.

Verification boundary

The finite edge sets and degrees can be recomputed completely; general graph theorems and the handshaking identity have no attached formal Evidence.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Bind SimpleGraph, finite neighbor sets, degree, the empty graph, and the exact scope of the handshaking identity.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.