Graph Theory: Concepts and Definitions

• The order of a graph G is the cardinality of the set of vertices |V(G)|, equivalent to the number of vertices in G.
• A multigraph occurs when a graph has more than one edge connecting the same two vertices, called multiple or parallel edges.
• A hypergraph has edges that connect more than two vertices.
• Vertices x and y are adjacent (or neighbors) when they are the endpoints of the same edge.
• Two edges are adjacent (or neighbors) when they share the same endpoint, or vertex.
• A graph is complete if all its vertices are adjacent, and a complete graph Kn has n(n-1)/2 edges.
• The degree of a vertex corresponds to the number of vertices adjacent to it or the number of incident edges.

Directed Graphs

• In directed graphs, the out-degree of a vertex v corresponds to the number of divergent edges (that leave) that vertex.
• The in-degree corresponds to the number of convergent edges (that arrive) at that vertex.
• A sink is a vertex with a zero out-degree.
• A source is a vertex with a zero in-degree.
• A graph is regular if all its vertices have the same degree.
• A path between two vertices is a sequence of vertices or edges that connect.
• A path of k vertices is formed by k-1 edges, and k-1 is the length of the path.
• A path is simple if all the vertices that compose it are distinct.
• A circuit is a closed path or walk in which the initial and final vertices are the same.
• A cycle is a circuit where all vertices are distinct, except for the first and last.
• A graph is cyclic if it has at least one cycle.
• A Hamiltonian path contains each vertex of the graph exactly once.
• A graph corresponds to a Hamiltonian cycle.
• An Eulerian path contains each edge of the graph exactly once.
• A graph has an Eulerian circuit, which contains all its edges.
• A graph is connected if there is a path between any two vertices, requiring a minimum of n-1 edges for n vertices.
• In a totally disconnected graph, each vertex is an isolated component with no edges connecting it to other vertices.
• Every Eulerian graph is connected, and all its vertices have an even degree.

Digraphs

• A digraph is strongly connected if it is possible to reach any vertex from any other vertex, following the direction of the edges.
• A bipartite graph can be divided into two disjoint sets of vertices, such that every edge connects a vertex from one set to a vertex from the other.

Trees and Forests

• A tree is a connected, rootless, and acyclic graph.
• A forest is an acyclic undirected graph, composed of a union of trees.
• A subgraph is a graph formed by a subset of the vertices and edges of another graph.
• A spanning subgraph preserves the connections between a set of selected vertices, using only edges that belong to the original graph.
• A spanning tree is a subgraph that is a tree and contains all the vertices of the original graph.
• An induced subgraph contains a specific subset of vertices from the original graph and all the edges that connect those vertices.