24.1. Graph Theory Basics

In this section, we will introduce the basic terminologies related to graph theory. We will discuss different types of graphs and we will also discuss Euler's theorem.

This chunk serves as the introduction to graph theory. It states that the lecture will cover basic terms and concepts, including various types of graphs and significant theorems related to them. This overview sets the stage for deeper exploration of the subject matter.

Think of graph theory like a road map. Just like a road map has various routes connecting towns (vertices) and streets (edges), graph theory deals with connections and paths between points in different contexts.

A graph is a collection of two sets: a set of vertices (or nodes) and a set of edges. The set of vertices is denoted as V, which is a non-empty set. The set of edges is denoted as E and consists of edges of the form (v, w) where v, w ∈ V. This edge set could be empty: E = ∅.

A graph is defined in mathematical terms as having vertices and edges. The vertices can be thought of as points, while edges represent the connections between these points. Importantly, a graph cannot exist without at least one vertex, but it can have no edges.

Imagine a social network where each person is a vertex. The connections (friendships) between them are the edges. You can have a group of friends (vertices) without any connections, meaning they are all isolated from one another.

We have two types of graphs: directed graphs and undirected graphs. In directed graphs, edges have directions (arrows), meaning there is a starting point and an ending point. In undirected graphs, edges do not have any direction, indicating a two-way connection.

Directed graphs represent relationships where the direction matters (e.g., tweets or posts where the flow of information has an origin and destination), whereas undirected graphs allow for a reciprocal relationship, meaning both vertices are equally connected.

Think of directed graphs like a one-way street where you can only drive in one direction, while undirected graphs are like a two-way street that allows traffic in both directions. In social networks, a follower relation can be treated as a directed relationship, while mutual friendships represent undirected connections.

A simple graph has no self-loops, and at most one edge exists between any two nodes. In other words, there are no multiple edges between the same two vertices.

A simple graph is a straightforward concept that prevents complexities like having more than one edge connecting any two vertices. This helps in analysis and makes certain calculations easier, as you deal with a clear structure.

Consider a simple graph like a friendship map where each friend (vertex) is connected by a single line (edge). If you tried to connect two friends with multiple lines (indicating multiple friendships), it would complicate who knows whom.

In an undirected graph, a pair of vertices u, v are called adjacent if they are connected by an edge (u, v). Vertices u and v are also called neighbors. An edge e is incident with the nodes u, v if they are the endpoints of edge e.

This terminology outlines core concepts in undirected graphs, emphasizing how vertices relate to each other via edges. Understanding these terms is crucial for discussing graph properties and analyzing their structure.

Imagine vertices as houses and edges as streets connecting them. If two houses share a street, they are neighbors (adjacent). A specific street (edge) connects these houses, acting as an incident item to these vertices.

The degree of a vertex v is defined as the number of edges incident with v. For vertices with self-loops, each self-loop counts as two.

Calculating the degree of a vertex is essential in understanding its connectivity within the graph. The degree provides information about how many connections a specific vertex has, influencing various graph characteristics.

Think of each vertex as a person at a party. The degree shows how many friends each person interacts with. If someone has a self-loop (a self-invitation), it counts twice — they really like their own company!

In any undirected graph, the sum of the degrees of all vertices is twice the number of edges. This is known as the handshaking theorem.

This theorem manifests a fundamental property in undirected graphs, emphasizing that each edge contributes to the degree count of two vertices. Hence, the total degree calculation is always even, as each edge pairs two vertices.

If you envision each edge as a handshake, each handshake involves two people. Thus, if you count all handshakes, each one shows up twice — once for each person involved.

In any undirected graph, the number of vertices with odd degrees is always even. This conclusion stems from the handshaking theorem.

This point illustrates that while certain vertices may connect unevenly, their total count will always balance out to an even number. It’s a fascinating property that sheds light on the structural makeup of graphs.

Imagine a classroom where students form pairs to work together. If a few students don’t have partners (odd degree), the total number of odd-degree students must be even because they can only form pairs together.

We define specific types of graphs such as complete graphs, cycle graphs, and wheel graphs. A complete graph has one edge between every pair of vertices, while cycle and wheel graphs represent specific configurations of connections.

This segment introduces specialized graph types, highlighting how connectivity can vary. A complete graph is fully connected, while cycle graphs create loops, and wheel graphs combine cycles with a central connecting point.

Visualize a group of friends (vertices) at a party. In a complete graph, everyone knows each other. A cycle graph is a group of friends who only interact in a circle, while a wheel graph has a star (central vertex) connected to each friend.

A graph is bipartite if its vertices can be divided into two distinct sets, such that no two graph vertices in the same set are adjacent.

Bipartite graphs illustrate relationships where interactions strictly occur between two different groups, with no connections within each group. This property is vital in modeling scenarios like job assignments where candidates and jobs interact.

Imagine a matchmaking service where candidates (one vertex set) and jobs (another vertex set) are linked. Candidates don’t interact with one another but only with job opportunities, making it a perfect bipartite graph scenario.

In a complete bipartite graph, every vertex in one part of the bipartition is connected to every vertex in the other part.

This type of graph enhances the bipartite structure by ensuring maximum connectivity between both sets. All possible edges exist between them, highlighting the relationships between two distinct groups.

Think of a classroom project where students (one set) must present ideas to different topics (another set). Each student must present to every topic — hence, a complete bipartite graph where every student connects to every topic.

--