graph

a graph is an ordered pair , where is a set whose elements are called vertices, and is a set of paired vertices, whose elements are called edges

consider the graph

a simple graph is a complete graph if for each two vertices we have .

a simple graph is an undirected graph with no parallel edges and no loops.

a directed graph is a graph whose edges are all directed. otherwise the graph is undirected.

an acyclic graph is a graph that contains no cycles.

an undirected graph is connected if between every two vertices there's a path.

a graph is called connected if it is non-empty and any two of its vertices are linked by a path in . if and is connected, we also call itself connected (in ). instead of 'not connected' we usually say 'disconnected'.

usually a graph is stored in computer memory using an adjacency list, this is the assumption here.

consider the following algorithm which receives an undirected graph and returns a list of its edges

the time complexity of this algorithm is

the maximum number of edges in a simple undirected graph is

in a complete graph, the rank of each vertex is , and it follows trivially that the sum of ranks is , and since each vertex touches 2 edges, the number of edges is .

let be a path in a graph

if , then is a cycle
a path is simple if no vertex appears in more than once
a cycle is simple if no vertex except for the first one appears in more than once
let be two paths in the graph , the concatenation of is

given a graph , the deletion of an edge results in the graph . the deletion of a vertex results in the graph where is equal to with any edges that were incident to removed.

the deletion of a set of vertices or edges can be denoted by .