Understanding of basic graphs and language

Introduction to Basic Graph Theory

Graphs are mathematical structures used to model pairwise relations between objects.
A graph in this context comprises vertices (or nodes) which are connected by edges (or arcs).
An edge connects two vertices to represent a relationship. The two vertices are called endpoints.
If the edges of a graph have a direction, it’s known as a directed graph or digraph; otherwise, it’s an undirected graph.
The order of a graph is the number of its vertices, and the size is the number of its edges.
A loop is an edge which connects a vertex to itself. A graph with at least one loop is a pseudograph.
An edge is considered incident to a vertex if the edge connects that vertex to another vertex or to itself in the case of a loop.
A graph without loops or multiple edges connecting the same pair of vertices is known as a simple graph.

Graph Characteristics and Parameters

The degree of a vertex is the number of edges incident to it, with loops being counted twice. In digraphs, we distinguish between the in-degree (number of incoming edges) and out-degree (number of outgoing edges).
A graph is regular if each vertex has the same degree.
The adjacency matrix stores the relationships between vertices with entries corresponding to the number of edges connecting a pair of vertices.
A path in a graph is a sequence of vertices where each adjacent pair is connected by an edge. A cycle is a path that starts and ends at the same vertex and includes at least one other vertex.
A graph is connected if there is a path between every pair of vertices.

Special Types of Graphs

A complete graph contains an edge between every pair of vertices. A complete graph with n vertices is denoted by Kᵢ where i is the number of vertices.
A bipartite graph can split its set of vertices into two disjoint sets such that all edges connect a vertex in one set to a vertex in the other set.

Graph Operations

Graphs can be altered via varieties of operations such as creating a subgraph, merging with another graph, and forming a complementary graph.
A subgraph is a portion of a graph, which includes some (or all) the vertices and some (or all) of the edges.
The complement of a graph G, denoted by G̅, is a graph with the same vertices as G but with edges that are not in G.
The union of two graphs is a graph that includes all the vertices and edges of both.
The intersection of two graphs is a graph that includes only the vertices and edges that both graphs have in common.

By being familiar with these basic definitions and operations, you can start to explore more complex concepts in graph theory such as graph isomorphism, graph colouring, and network theory.