10.1 Basic concepts and definitions in graph theory

A vertex is a fundamental unit in graph theory, representing a point or a node where edges connect. It plays a crucial role in defining the structure of a graph, as vertices are the entities that can be connected by edges, forming the basis for various types of graphs, such as trees and planar graphs. The connections between vertices help illustrate relationships and interactions within different contexts.

Edge: An edge is a line segment connecting two vertices in a graph, representing a relationship or connection between them.

Degree: The degree of a vertex is the number of edges incident to it, indicating how many connections that vertex has to other vertices.

Graph: A graph is a collection of vertices and edges, used to model pairwise relationships between objects.

An edge is a fundamental component of a graph that connects two vertices, representing a relationship or connection between them. Edges can be either directed or undirected, impacting how relationships are analyzed within the graph. They play a crucial role in defining the structure and properties of graphs, which influences concepts like degree sequences, connectivity, and traversal.

Vertex: A vertex is a fundamental unit in a graph, representing an endpoint or a node where edges meet.

Degree: The degree of a vertex is the number of edges incident to it, indicating how many connections it has within the graph.

Graph: A graph is a collection of vertices and edges that represents relationships between objects or entities.

A simple graph is a type of graph in which each pair of vertices is connected by at most one edge, and no edge connects a vertex to itself. This means that there are no loops or multiple edges between the same pair of vertices. Simple graphs provide a foundational understanding of graph theory and are critical for exploring concepts like degree sequences and the Handshaking Lemma.

Vertex: A vertex is a fundamental unit of a graph, representing an endpoint where edges meet.

Edge: An edge is a connection between two vertices in a graph, representing relationships or links between them.

Degree: The degree of a vertex is the number of edges incident to it, indicating how many connections that vertex has within the graph.

A multigraph is a type of graph that allows multiple edges (or parallel edges) between the same pair of vertices, distinguishing it from simple graphs where only one edge can exist between two vertices. This flexibility enables the representation of more complex relationships in networks, such as social connections or transportation systems, where several routes may exist between two points. Multigraphs can also include loops, which are edges that connect a vertex to itself.

Vertex: A vertex (or node) is a fundamental unit in a graph, representing an endpoint or junction where edges meet.

Edge: An edge is a connection between two vertices in a graph, representing a relationship or pathway between them.

Simple Graph: A simple graph is a type of graph that does not allow multiple edges between the same pair of vertices and does not include loops.

In graph theory, in-degree refers to the number of edges directed into a vertex in a directed graph. It helps understand the flow of information or resources within networks and is essential for analyzing the structure and behavior of directed graphs. The concept of in-degree is closely related to out-degree, which counts edges leaving a vertex, and plays a crucial role in degree sequences and the Handshaking Lemma.

out-degree: The number of edges leaving a vertex in a directed graph.

degree sequence: A list of the degrees of all vertices in a graph, typically arranged in non-increasing order.

Handshaking Lemma: A theorem stating that the sum of the degrees of all vertices in an undirected graph is equal to twice the number of edges.

Out-degree is the number of edges that originate from a particular vertex in a directed graph. This concept is essential in understanding the structure and flow of information within directed graphs, where the direction of edges indicates the relationships or connections between vertices. The out-degree can help analyze the connectivity of a vertex, and it plays a critical role in various applications, such as network theory, where it can influence how data or resources are distributed.

in-degree: In-degree is the number of edges that terminate at a particular vertex in a directed graph, indicating how many vertices point to it.

degree sequence: Degree sequence is a list of the degrees of all vertices in a graph, often used to analyze and characterize the properties of graphs.

directed graph: A directed graph is a set of vertices connected by directed edges, where each edge has a direction indicating a one-way relationship between two vertices.

An adjacency matrix is a square grid used to represent a finite graph, where the rows and columns correspond to the graph's vertices, and the entries indicate whether pairs of vertices are adjacent or not. This representation is useful for performing various graph-related algorithms and analyzing the structure of the graph. It provides a clear way to visualize connections and can help identify properties such as graph isomorphisms and aid in shortest path calculations.

Graph: A collection of vertices connected by edges, which can be directed or undirected.

Degree of a Vertex: The number of edges incident to a vertex in a graph, which can indicate how connected the vertex is within the structure.

Path: A sequence of edges connecting a sequence of vertices in a graph, which can be used to determine connectivity and distance between vertices.

An incidence matrix is a mathematical representation of a graph, where the rows correspond to the vertices and the columns correspond to the edges. Each entry in the matrix indicates the relationship between a vertex and an edge, typically using a 1 or 0 to show whether the vertex is incident to that edge. This type of representation is useful for analyzing graph properties and is essential for understanding graph isomorphisms.

adjacency matrix: An adjacency matrix is another way to represent a graph, where the rows and columns represent vertices, and entries indicate whether pairs of vertices are adjacent.

graph isomorphism: Graph isomorphism refers to a condition where two graphs can be transformed into one another by renaming vertices while preserving connectivity.

degree of a vertex: The degree of a vertex in a graph is the number of edges connected to it, indicating how many direct connections it has.

In graph theory, the degree of a vertex is defined as the number of edges that are incident to that vertex. It indicates how many connections a particular vertex has within a graph, serving as a crucial measure of its connectivity and importance. The degree can be used to classify vertices in terms of their roles, such as whether they are more central or peripheral within the graph structure.

Vertex: A fundamental unit in a graph, representing an endpoint where edges meet.

Edge: A connection between two vertices in a graph that represents a relationship or interaction.

Path: A sequence of edges that connect a sequence of vertices without repeating any vertex.

The handshaking lemma states that in any undirected graph, the sum of the degrees of all vertices is twice the number of edges. This result emphasizes the relationship between vertex degrees and edges, serving as a foundational concept in graph theory. It connects to various aspects such as degree sequences, path properties, and the structure of graphs.

Degree of a Vertex: The degree of a vertex is the number of edges incident to it, indicating how many connections it has in a graph.

Eulerian Path: An Eulerian path is a trail in a graph that visits every edge exactly once, which exists if there are exactly zero or two vertices of odd degree.

Hamiltonian Cycle: A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

An isolated vertex is a vertex in a graph that has no edges connecting it to any other vertices. This means that the isolated vertex stands alone and does not participate in the connectivity of the graph. Understanding isolated vertices helps in analyzing the structure of graphs, especially in relation to concepts like connected components and graph connectivity.

vertex: A vertex is a fundamental unit of a graph, representing a point where edges meet.

edge: An edge is a connection between two vertices in a graph, representing a relationship or link.

connected component: A connected component is a subset of a graph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

In graph theory, a path is a sequence of vertices where each adjacent pair is connected by an edge. Paths are fundamental in analyzing graphs as they help describe how one can traverse from one vertex to another. Understanding paths is crucial when exploring concepts such as connectivity, cycles, and various properties of graphs.

Cycle: A cycle is a path that starts and ends at the same vertex, with all other vertices in the path being distinct.

Walk: A walk is a sequence of vertices and edges in which vertices can repeat, allowing for more flexible traversal of the graph.

Degree: The degree of a vertex is the number of edges connected to it, providing insight into the structure and connectivity of the graph.

A cycle in graph theory is a path that starts and ends at the same vertex, containing at least one edge, and no other vertices are repeated. This concept is central to understanding the structure of graphs, as cycles can indicate connectivity and the presence of feedback loops. In degree sequences and the Handshaking Lemma, cycles help in analyzing how vertices are interconnected through edges, while in paths, walks, and more complex graph behaviors, cycles reveal important properties regarding traversals.

Path: A sequence of edges connecting a sequence of distinct vertices in a graph without repetition.

Walk: A sequence of vertices and edges in a graph where vertices and edges may be repeated.

Eulerian Cycle: A cycle that visits every edge of a graph exactly once and returns to the starting vertex.

An Eulerian path is a trail in a graph that visits every edge exactly once. This concept plays a crucial role in understanding the structure of graphs and their connectivity, linking to various properties such as degrees of vertices and cycles. Eulerian paths can exist in graphs with specific configurations of vertex degrees, making them fundamental to problems in network design and route optimization.

Eulerian Circuit: An Eulerian circuit is a special case of an Eulerian path that starts and ends at the same vertex while visiting every edge exactly once.

Graph Connectivity: Graph connectivity refers to the minimum number of vertices or edges that need to be removed to disconnect the remaining vertices from each other, influencing the existence of Eulerian paths.

Degree of a Vertex: The degree of a vertex is the number of edges incident to that vertex, which determines whether an Eulerian path can exist based on the parity of the degrees.

A Hamiltonian path is a path in a graph that visits each vertex exactly once. It is named after the mathematician William Rowan Hamilton and is a crucial concept when analyzing the structure and characteristics of graphs, particularly in relation to paths, cycles, and walks. Understanding Hamiltonian paths helps to explore more complex structures like Hamiltonian cycles, which return to the starting vertex, and connects to broader principles of graph theory.

Hamiltonian Cycle: A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

Graph Theory: Graph theory is a branch of mathematics that studies the properties and interactions of graphs, which consist of vertices and edges.

Eulerian Path: An Eulerian path is a trail in a graph that visits every edge exactly once. It differs from a Hamiltonian path, which focuses on visiting vertices.

In graph theory, a component refers to a maximal connected subgraph of a graph, meaning that there is a path between any two vertices within this subgraph. Components can be understood as the building blocks of a graph, determining how the vertices are interrelated through edges. The study of components is essential for analyzing the structure of graphs, as they reveal important properties about connectivity and the overall arrangement of vertices and edges.

Connected Graph: A graph is connected if there is a path between every pair of vertices, meaning that it consists of a single component.

Disconnected Graph: A graph that has at least two components; there are pairs of vertices that cannot be connected by any path.

Subgraph: A subgraph is a graph formed from a subset of the vertices and edges of another graph, which may or may not be connected.

A subgraph is a portion of a graph that consists of a subset of its vertices and edges, essentially creating a new graph from an existing one. It retains the original graph's structure while allowing for the exploration of specific components or relationships within that graph. Understanding subgraphs is crucial for analyzing more complex structures, as they often reveal important properties and patterns present in the larger graph.

Vertex: A vertex is a fundamental unit in a graph, representing an endpoint or a node in the structure, which can be connected by edges.

Edge: An edge is a connection between two vertices in a graph, representing a relationship or pathway between them.

Induced Subgraph: An induced subgraph is formed by taking a subset of vertices from the original graph and including all the edges that connect those vertices.

In graph theory, a bridge is an edge in a graph whose removal increases the number of connected components, essentially disconnecting the graph. Bridges play a crucial role in understanding the connectivity of a graph, as they identify critical connections that, if severed, can isolate parts of the graph. This concept is tied to the broader study of graph properties such as connectivity and cut vertices.

cut vertex: A cut vertex is a vertex in a graph whose removal increases the number of connected components, similar to how a bridge operates but focused on vertices instead of edges.

connected graph: A connected graph is one where there is a path between every pair of vertices, meaning the graph remains intact without any isolated components.

component: A component is a maximal connected subgraph of a given graph, where there are no additional edges that can be added without losing the property of connectivity.

An articulation point, also known as a cut vertex, is a vertex in a graph whose removal increases the number of connected components of the graph. This means that if you take out an articulation point, it disconnects the graph into two or more parts, which highlights its critical role in maintaining connectivity within the structure of the graph. Understanding articulation points helps in analyzing the robustness of networks and designing strategies to enhance their resilience against failures.

Connected Graph: A connected graph is a graph where there is a path between every pair of vertices, ensuring that all vertices are reachable from one another.

Bridges: Bridges are edges in a graph that, when removed, increase the number of connected components, similar to how articulation points affect connectivity at the vertex level.

DFS (Depth-First Search): DFS is an algorithm for traversing or searching tree or graph data structures, which can be utilized to identify articulation points through its traversal process.