Relationship Between Degrees of Vertices and Edges in a Graph

Introduction

• Discusses the correlation between the degrees of vertices and the number of edges in a graph.
• Utilizes a simple graph to explain the concept.

Example 1: Simple Graph

• Graph Description: Two towns connected by a single road.
• Degree of Vertices:
  • Each vertex has a degree of 1 (one edge connected to each vertex).
  • Total degrees = 1 + 1 = 2.
• Number of Edges:
  • There is 1 edge (road) between the towns.

Example 2: Adding Complexity

• Graph Description: Added a vertex, a road, and a loop.
• Degree of Vertices:
  • Vertex 1: Degree 2
  • Vertex 2: Degree remains 1
  • Vertex 3: Degree 1 + loop = 3
  • Total degrees = 2 + 1 + 3 = 6.
• Number of Edges:
  • Total edges = 3 (including the loop).

Example 3: Further Complexity

• Graph Description: Introduced additional vertices and more edges.
• Degree of Vertices:
  • Vertex 1: Degree 4
  • Vertex 2: Degree 3
  • Vertex 3: Degree 2
  • Vertex 4: Degree 3
  • Total degrees = 4 + 3 + 2 + 3 = 12.
• Number of Edges:
  • Total edges = 6.

Conclusion

• Observation: Pattern emerges as the sum of the degrees of all vertices.
• Key Insight:
  • The sum of the degrees of the vertices in a graph is always double the number of edges.
  • Relationship: Total degrees = 2 * Number of edges.
• Reason: Each edge contributes to the degree of two vertices.