^^Grafo.

A graph, sometimes called

is a pair G = (V, E)

vertices of an edge ≡ endpoints of the edge.

The edge {x, y} is said to join x and y and to be incident on x and y.

A vertex may belong to no edge, in which case it is not joined to any other vertex.

loop : an edge that join a vertex to itself

parallel edges : join the same vertices

simple graph : no loops, no paralle edges. each edge connects two distinct endpoints and no two edges have the same endpoints.

In many cases, graphs are assumed to be simple unless specified otherwise.

simple edge : no parallel edges.

simple path or simple cycle : a path or cycle that has no repeated vertices and consequently no repeated edges.

degree of a vertex in a graph: the number of its incident edges.

(in an undirected graph) the sum of the degrees of all vertex equals twice the number of edges.

dim: 1 edge ↔ +2 degree

nodes = vertex

path Path_(graph_theory)

a sequence of edges which joins a sequence of distinct vertices, exept

closed path : same first and last vertex.

Since the vertices are distinct but 1, so are the edges.

walk : vertici con possibili ripetizioni.

trail : vertici distinti

es: if a graph has n vertices, then how many edges can it have without any three of them forming a triangle?

In general, questions in extremal combinatorics ask

Szemerédi's theorem itself is another example:

how many numbers you can choose between 1 and n before you are forced to include an arithmetic progression of length k.

gowers/pdf The work of Endre Szemerédi, Abel price 2012