graph

a graph is an ordered pair $\text{[math]}$ , where $\text{[math]}$ is a set whose elements are called vertices, and $\text{[math]}$ is a set of paired vertices, whose elements are called edges

consider the graph $\text{[math]}$
$\text{[math]}$

a simple graph is a complete graph if for each two vertices we have $\text{[math]}$ .

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 $\text{[math]}$ is connected if between every two vertices there's a path.

a graph $\text{[math]}$ is called connected if it is non-empty and any two of its vertices are linked by a path in $\text{[math]}$ . if $\text{[math]}$ and $\text{[math]}$ is connected, we also call $\text{[math]}$ itself connected (in $\text{[math]}$ ). instead of 'not connected' we usually say 'disconnected'.
[cite:;taken from @graph_diestel_2017 chapter 1.4 connectivity]

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
$\text{[math]}$ the time complexity of this algorithm is $\text{[math]}$

$\text{[math]}$

the maximum number of edges in a simple undirected graph is
$\text{[math]}$

in a complete graph, the rank of each vertex is $\text{[math]}$ , and it follows trivially that the sum of ranks is $\text{[math]}$ , and since each vertex touches 2 edges, the number of edges is $\text{[math]}$ .

let $\text{[math]}$ be a path in a graph $\text{[math]}$

if $\text{[math]}$ , then $\text{[math]}$ is a cycle
a path $\text{[math]}$ is simple if no vertex appears in $\text{[math]}$ more than once
a cycle $\text{[math]}$ is simple if no vertex except for the first one appears in $\text{[math]}$ more than once
let $\text{[math]}$ be two paths in the graph $\text{[math]}$ , the concatenation of $\text{[math]}$ is $\text{[math]}$

given a graph $\text{[math]}$ , the deletion of an edge $\text{[math]}$ results in the graph $\text{[math]}$ . the deletion of a vertex $\text{[math]}$ results in the graph $\text{[math]}$ where $\text{[math]}$ is equal to $\text{[math]}$ with any edges that were incident to $\text{[math]}$ removed.
the deletion of a set of vertices or edges can be denoted by $\text{[math]}$ .