Elements of Graph Theory

Elements of Graph Theory

Graph theory is a field of mathematics that deals with graphs, which are mathematical structures used to model pairwise relations between objects. It is widely applied in fields like computer science, social network analysis, transportation, and more. Below are the core elements of graph theory, which help define the structure and properties of graphs:

---

1. Graph

A graph is defined by a set of vertices (or nodes) and a set of edges (or arcs) that connect pairs of vertices.

• Graph Representation: A graph is often represented as $G = (V, E)$, where:
  • $V$ is the set of vertices (nodes).
  • $E$ is the set of edges (connections between vertices).

---

2. Vertices (Nodes)

• Vertex (or Node): A vertex is a fundamental unit of a graph, representing an entity in the system. Vertices are the points or positions in the graph.
  • Example: In a social network graph, a vertex could represent a person.

---

3. Edges (Arcs)

• Edge (or Arc): An edge is a connection between two vertices. Edges can be:

  • Directed (in a directed graph), where the edge has a direction from one vertex to another.
  • Undirected (in an undirected graph), where the edge has no direction and simply connects two vertices.

• Edge Representation: An edge is typically represented as a pair (or set) of vertices, such as $(u, v)$ or $\{u, v\}$, depending on whether the graph is directed or undirected.

  • In a directed graph, an edge is represented as $(u, v)$, meaning there's a directed edge from vertex $u$ to vertex $v$.
  • In an undirected graph, an edge is represented as $\{u, v\}$, meaning there's an undirected edge between vertices $u$ and $v$.

---

4. Degree of a Vertex

The degree of a vertex refers to the number of edges connected to it.

• In-degree: In a directed graph, the in-degree of a vertex is the number of edges directed toward the vertex.
• Out-degree: In a directed graph, the out-degree of a vertex is the number of edges that originate from the vertex.
• Total degree: In an undirected graph, the degree is simply the number of edges connected to a vertex.
  • In a directed graph, the total degree of a vertex is the sum of its in-degree and out-degree.

---

5. Path and Walk

A path in a graph is a sequence of vertices in which each consecutive pair of vertices is connected by an edge.

• Walk: A walk is a sequence of vertices where each pair of consecutive vertices is connected by an edge, but vertices and edges can be repeated.
• Path: A path is a walk where no vertex (and sometimes no edge) is repeated.
• Cycle: A cycle is a path that starts and ends at the same vertex, without repeating any other vertices.

---

6. Types of Graphs

Graphs come in different types based on their properties and structures:

• Undirected Graph: A graph in which edges have no direction. An edge $\{u, v\}$ indicates that both $u$ and $v$ are connected.
• Directed Graph (Digraph): A graph in which edges have a direction, represented as ordered pairs $(u, v)$, indicating a directed edge from vertex $u$ to vertex $v$.
• Weighted Graph: A graph in which each edge has a weight or cost associated with it, often representing distances, costs, or capacities.
• Simple Graph: A graph that has no loops (edges from a vertex to itself) and no more than one edge between any two vertices.
• Multigraph: A graph that may have multiple edges between the same pair of vertices, including loops.
• Complete Graph: A graph in which there is an edge between every pair of distinct vertices. A complete graph with $n$ vertices is denoted as $K_n$.
• Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set.
• Planar Graph: A graph that can be drawn on a plane without any edges crossing each other.

---

7. Subgraphs

• Subgraph: A subgraph of a graph $G = (V, E)$ is a graph formed by selecting a subset of the vertices $V' \subseteq V$ and a subset of the edges $E' \subseteq E$ such that for every edge in $E'$, both of its endpoints are in $V'$.
• Induced Subgraph: The induced subgraph is the graph formed by selecting a subset of vertices and including all the edges that connect pairs of vertices in this subset.

---

8. Connectedness

A graph is considered connected if there is a path between every pair of vertices.

• Connected Graph: In an undirected graph, the graph is connected if there is a path between every pair of vertices.
• Disconnected Graph: A graph is disconnected if it is not connected, i.e., there exists at least one pair of vertices with no path between them.
• Strongly Connected Graph: A directed graph is strongly connected if there is a directed path from every vertex to every other vertex.
• Weakly Connected Graph: A directed graph is weakly connected if, by ignoring edge directions, the graph is connected.

---

9. Components

• Component: A component of a graph is a maximal connected subgraph. A component is a subgraph in which there is a path between every pair of vertices, and no additional vertices from the graph can be added to the subgraph while maintaining connectivity.
  • In a disconnected graph, there are multiple components.

---

10. Trees and Forests

• Tree: A tree is a connected, acyclic graph. A tree with $n$ vertices has $n - 1$ edges.

  • Rooted Tree: A tree with a designated root vertex, from which all other vertices are accessible.
  • Leaf: A leaf is a vertex in a tree that has no children (degree of 1).
  • Parent/Child: In a rooted tree, a vertex that has an edge directed toward another vertex is the parent, and the other vertex is the child.

• Forest: A forest is a disjoint set of trees (i.e., an acyclic graph that may be disconnected).

---

11. Eulerian and Hamiltonian Graphs

• Eulerian Graph: A graph is Eulerian if there exists a cycle that visits every edge exactly once. A necessary and sufficient condition for an undirected graph to be Eulerian is that all vertices have an even degree.
• Hamiltonian Graph: A graph is Hamiltonian if there exists a cycle that visits every vertex exactly once. There is no simple criterion for a graph to be Hamiltonian.

---

12. Isomorphism

• Graph Isomorphism: Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there is a one-to-one correspondence between their vertices and edges that preserves the adjacency relation.

---

13. Adjacency Matrix and List

• Adjacency Matrix: An adjacency matrix is a square matrix used to represent a graph. The element at row $i$ and column $j$ indicates whether there is an edge between vertices $v_i$ and $v_j$.

  • In an undirected graph, the matrix is symmetric.
  • In a directed graph, the matrix is not necessarily symmetric.

• Adjacency List: An adjacency list is a collection of lists or arrays where each vertex has a list of adjacent vertices (i.e., vertices that it is directly connected to by an edge).

---

14. Degree Sequence

• Degree Sequence: The degree sequence of a graph is a list of the degrees of all the vertices in the graph, usually sorted in non-increasing order.

---

15. Matching and Bipartite Matching

• Matching: A matching is a set of edges in which no two edges share a common vertex.
• Bipartite Matching: A bipartite matching is a matching in a bipartite graph where the vertices are divided into two disjoint sets, and each edge connects a vertex from one set to a vertex from the other set.

---

Summary Table

Element	Description
Graph	A collection of vertices and edges.
Vertex	A point in a graph.
Edge	A connection between two vertices.
Degree of Vertex	The number of edges connected to a vertex.
Path	A sequence of vertices connected by edges.
Cycle	A path that starts and ends at the same vertex.
Connected Graph	A graph in which there is a path between every pair of vertices.
Tree	A connected, acyclic graph.
Eulerian Graph	A graph with a cycle that visits every edge exactly once.
Hamiltonian Graph	A graph with a cycle that visits every vertex exactly once.
Isomorphism	A one-to-one correspondence between two graphs preserving adjacency.
Matching	A set of edges with