24.1.4. Terminologies related to Undirected Graphs

If you are given an undirected graph then a pair of vertices u, v are called adjacent or neighbors of each other. If the edge (u, v) ∈ E, then we call the vertices u and v to be adjacent or neighbors.

In an undirected graph, two vertices are said to be adjacent if there exists an edge connecting them. This concept helps us understand the relationship between vertices. For example, if there is an edge between vertex u and vertex v, they are adjacent. If a vertex has a self-loop, it is also considered adjacent to itself because it connects back to itself.

Think of a social network where people (vertices) are connected by friendships (edges). If two people are friends, they are adjacent in the graph representing the network. Moreover, if someone is friends with themselves (like having a self-loop), they are considered adjacent to themselves in that context.

If we are given an edge e, then we will say that it is incident with the nodes u, v if u and v are the end points of the edge.

In graph theory, an edge is said to be incident to its endpoints. This means that if you have an edge e connecting vertices u and v, we say that the edge is incident to u and v. This concept is essential to understand how edges and vertices interact in a graph.

Imagine a bridge (the edge) connecting two islands (the vertices). The bridge is said to be 'incident' to the two islands because it directly connects them. Without the bridge, the islands would not have a direct connection.

The degree of a vertex v is the number of edges incident with v or, in simpler terms, the number of edges that have v as one of their endpoints.

The degree of a vertex indicates how many edges are connected to it. For example, if vertex v has three edges connecting to it, then the degree of vertex v is 3. It's important to note that self-loops contribute twice to the degree, as they connect the vertex to itself.

Consider a person who has friends (edges) in a social circle. If a person has 5 friends, their degree is 5. If one of those friends is also their sibling (a self-loop in this context), it indicates a deeper connection, increasing their overall connections (degree) to 6.

The handshaking theorem states that the sum of the degrees of all the vertices in an undirected graph is twice the number of edges.

This theorem is a fundamental concept in graph theory. For any edge in the graph, it contributes 1 to the degree count of each of its endpoints. Therefore, when summing the degrees of all vertices, each edge is counted twice, leading to the conclusion that the total degree sum is twice the number of edges.

Imagine a party where each attendee shakes hands with others. If one person shakes hands with 3 others, they contribute 3 to the total handshake count, and those 3 will each count the handshake back to that person. Thus, if you sum all handshakes, you’ll count each interaction twice, leading to the conclusion stated in the theorem.

The theorem states that the number of vertices of odd degree in an undirected graph is always even.

This conclusion results from the handshaking theorem. If you sum the degrees of all vertices and find the sum is even, the odd degree vertices must come in pairs to keep the total sum even. Therefore, there cannot be an odd number of vertices with odd degrees.

Think about a game where players must form pairs to strategize. If there are players with an odd number of connections in the game, they'll always require an additional player to pair up, which means there must be at least two players with odd connections to maintain game balance.

--