In this page, I will briefly describe on the list of terminologies that are commonly used in Graph Theory. I will explain directly on this page about the simple concept, but I will write a separate pages that would require long/detailed explanation.

• Adjacency Matrix
• Degree
• Distance
• Eulerian Cycle/Circuit
• Hamiltonion Path/Cycle
• Incidence Matrix
• Path and Cycle
• Size
• Vertex and Edge

Vertex and Edge

In the realm of graph theory, two fundamental concepts are indispensable: vertices and edges. Vertices, also known as nodes, represent discrete entities or points, which can symbolize various real-world elements such as cities, people, or data points. Edges, the connections between these vertices, denote the relationships or interactions between these entities. This framework of vertices connected by edges allows for the modeling and analysis of networks in many fields, including computer science, biology, and social science, providing valuable insights into the structure and dynamics of complex systems.

• Vertex (Vertices): In graph theory, a vertex (or node) is a fundamental unit from which graphs are formed. In the above diagram, each purple circle represents a vertex. Vertices can be used to represent objects, locations, or entities in various applications.
• Edge: An edge is a line connecting two vertices in a graph. It represents a relationship or connection between the vertices. In the above diagram, the green lines are edges. Edges can be undirected (no directionality) or directed (having a direction), though the ones in your image appear to be undirected.

Degree 

The degree of a vertex in graph theory is a fundamental metric that quantifies the number of edges incident to a vertex, essentially measuring its connectivity within the graph. This concept plays a pivotal role in understanding the structure and behavior of networks, providing insights into the complexity and robustness of the networked system. Whether in analyzing social networks, optimizing transportation routes, or designing efficient communication systems, the degree of a vertex serves as a key analytical tool in numerous applications.

• Degree of a Vertex: The degree of a vertex in a graph is defined as the number of edges connected to that vertex. It quantifies the immediate connectivity of a vertex within the graph.

Size

This size of a graph is a basic yet crucial characteristic that describes how many points or nodes are present in a graph. The size of a graph is instrumental in understanding its complexity and the potential for connections among nodes, affecting both the theoretical properties and practical applications of the graph in various domains such as network analysis, algorithm design, and computational biology.

Path and Cycle

In graph theory, understanding the structure and relationships within a network often revolves around two key concepts: paths and cycles. A path in a graph is defined as a sequence of vertices connected by edges where each vertex is visited exactly once, except possibly the first and last vertices. This structure is crucial for problems involving traversal, routing, and connectivity. On the other hand, a cycle represents a path whose starting and ending vertices are the same, creating a loop. Cycles are particularly significant because they can indicate redundancy in networks, circulation in flow systems, or feedback loops in circuit designs. Together, paths and cycles form the backbone of many algorithms and are essential for analyzing and interpreting the behavior of complex networks.

• Path: A path in a graph is a sequence of edges that connects a sequence of distinct vertices, where no vertex is visited more than once. In the above graph, the route highlighted with the red dashed line represents a path. It begins at one vertex and ends at another distinct vertex, without repeating any vertices along the route. This path is used to demonstrate a simple journey from a starting point to an endpoint, which is common in scenarios like routing and navigation.
• Cycle: A cycle is a path in which the start vertex and end vertex are the same, forming a closed loop. This means that the path returns to its original starting point. In the above graph, the cycle is indicated by the yellow dashed line. The cycle covers multiple vertices and returns to the starting vertex, creating a loop. This concept is crucial in applications like network design and circuit testing, where returning to the starting point without revisiting any other vertex is necessary.

Hamiltonion Path/Cycle

A Hamiltonian path in a graph is a path that visits each vertex exactly once. If this path returns to the starting vertex, forming a closed loop, it is called a Hamiltonian cycle. These constructs are important for understanding complex connectivity and routing problems, such as in logistics or network design, where each point (or vertex) needs to be visited precisely once.

These Hamiltonian paths and cycles are vital for solving problems where you must visit every point or node once without repetition, like in certain puzzles, scheduling tasks, or even the famous "Traveling Salesman Problem" in optimization discussions. Understanding these concepts can provide deep insights into the complexity and tractability of network routing challenges.

• Hamiltonian Path:
• The Hamiltonian path connects all the vertices in the graph without revisiting any. This path does not close back on itself, meaning it starts and ends at different vertices.
• In the graph above, the path is marked with green edges that connect all the purple vertices exactly once without forming a loop.
• Hamiltonian Cycle:
• The Hamiltonian cycle also visits each vertex exactly once but differs from the path by returning to the starting vertex, thus forming a loop.
• In the graph above, This cycle is depicted with green edges that form a closed circuit, returning to the initial vertex after traversing all other vertices exactly once.

Eulerian Cycle/Circuit 

An Eulerian cycle, or Eulerian circuit, is a cycle in a graph which visits every edge exactly once. This cycle can start and end at the same vertex, encompassing all edges without repeating any. Eulerian cycles are a key concept in the study of graph theory and are particularly significant in solving real-world problems that involve traversing paths in an efficient manner, such as in the routing of garbage collection vehicles in cities or in postman routes where each road needs to be traveled exactly once.

Understanding Eulerian cycles is crucial for designing efficient algorithms in network routing and circuit design, ensuring minimal travel or movement while covering all necessary connections. This concept also helps in understanding the feasibility of constructing such paths or cycles in given graphs based on their structure and edge connectivity.

Distance

In graph theory, the distance between two vertices is defined as the minimum number of edges that must be traversed to travel from one vertex to the other. This metric is crucial for understanding the efficiency of connectivity within a network and is often used in applications such as routing, navigation, and network design. The shortest path represents the most direct route between the two points, minimizing the cost, time, or distance traveled.

For example, there are many different paths connecting the vertices A and B. But the number of edges on path 1 are used to calculate the distance because it goes through the least number of edges between A and B. The distance between A and B is 2 in this example.