Define the term Degree of a graph.

Definition:

In graph theory, the degree of a vertex is the number of edges incident to that vertex. The degree of a vertex is also known as its valency.

Mathematical Notation:

The degree of a vertex $v$ in a graph $G$ is denoted by $deg(v)$.

Types of Degrees:

• Total Degree: The total degree of a vertex is the sum of the degrees of all the vertices adjacent to it.

• In-Degree: For a directed graph, the in-degree of a vertex is the number of edges directed towards that vertex.

• Out-Degree: For a directed graph, the out-degree of a vertex is the number of edges directed away from that vertex.

Properties of Degree:

• Handshake Theorem: In a simple graph, the sum of the degrees of all the vertices is equal to twice the number of edges.

• Maximum and Minimum Degree: The maximum degree of a vertex in a graph is equal to the number of vertices minus one. The minimum degree of a vertex in a graph is zero.

• Regular Graph: A graph in which every vertex has the same degree is called a regular graph.

Significance of Degree:

• Vertex Connectivity: The degree of a vertex is an important factor in determining the vertex connectivity of a graph. A vertex with a high degree is less likely to be a cut vertex.

• Edge Connectivity: The degree of a vertex is also an important factor in determining the edge connectivity of a graph. A vertex with a high degree is less likely to be a bridge.

• Graph Coloring: The degree of a vertex is a key factor in determining the chromatic number of a graph. A graph with a high maximum degree will require more colors to color its vertices.

• Graph Algorithms: The degree of a vertex is often used in graph algorithms, such as depth-first search and breadth-first search.