Welcome to this blog post where we delve into the fundamental concepts of graph theory. We will revisit the definition of a graph and explore essential elements such as loops, edges, and the intriguing realm of simple graphs. By understanding these core concepts, we gain insights into the underlying structures that shape complex systems.
Refresher of graphs
A graph is a mathematical structure that consists of two main components: a finite set of vertices (V), which represent points or objects, and a finite set of edges (E), which represent connections or relationships between the vertices.
Definition 1.1 (graph)
A graph G is given by a finite set V of vertices and a finite set E of edges such that V ∩E = ∅.
It is also important to note that each vertices and edges are distinct and separate, without any overlap between them, this is what the V ∩E = ∅ part of the definition means.
Let us create an analogy to help us understand this. Imagine three friends: Alice, Bob and Charlie live close to each other. The houses are the vertices, and the roads connecting them are the edges. In this case, a graph represents the layout of the neighborhood.
It is also important to note that each house and road are distinct and separate, without any overlap between them.
We will use this analogy throughout this post to help us understand more complex properties of graphs.
Edges and Adjacent Vertices
We mentioned in our analogy that roads are edges, but what properties must an edge have to be considered an edge.
Definition 1.2 (edge)
Each edge in E is associated with two vertices in V called its endpoints We say that an edge is incident to both its endpoints, or between its endpoints
For two vertices u and v, we can use the notation (u,v) to mean the edge between them.
Each edge represents a direct connection or path between to vertices, such as in the figure above the vertices u and v are connected by an edge, we say that an edge is incident to its vertices. Using our analogy the road (edge) in the neighborhood connects two houses (vertices), serving as a pathway between them.
Definition 1.3 (adjacent vertices)
Two vertices u and v are adjacent or neighbors if there is an edge between u and v
In our neighborhood, two houses are considered adjacent or neighbors if there is a road directly connecting them. In figure 1.0 Alice, Bob and Charlie are all neighbors.
Simple Graph
Before we define a simple graph let us first write down a few more definitions to help us.
Definition 2.1 (loop)
An edge is a loop if both its endpoints are the same
This is exactly what it looks like, using our analogy if a house has a road that leads back to itself then we say that road (edge) is a loop. We can write a looped edge like (u,u).
Definition 2.2 (multiple edges)
A multiple edge exists if there are other edges with the same endpoints
Say we have two houses (vertices) u and v that are connected by a road (edge), if there exists more than one road (edge), between the two houses i.e. multiple roads between u and v, then we say there exists multiple edges.
Now we defined some key properties let us define what a simple graph is.
Definition 3.0 (simple graph)
A graph G is simple if (i) every edge in E(G) has two distinct endpoints and (ii) for every pair of vertices u, v ∈ V(G) there is at most one edge incident to both u and v.
This might sound confusing but we already covered both points, (i) in the above definition is simply stating that a road must have two unique houses as the endpoints and (ii) is saying there cant be multiple roads between two houses. In simpler words (forgive the pun) a graph G is simple if it does not contain any loops or multiple edges.
To visualize this, look at the below figure, it is clear that there exists multiple edges between the vertices u and v. So this can not be a simple graph.
Similarly below there exists a loop so this also can not be a simple graph.
We have explained what a simple graph is but there are a few more important properties of a simple graph we should mention.
Theorem 1.2
A simple graph with n vertices has at most n (ⁿ₂)
This is intuitive, if we have 2 vertices, then we have 1 edge between them, if we have 3 vertices then we would have 3 edges between them (following from our definitions). This pattern continues, and the expression (ⁿ₂) holds true, indicating that the number of edges in a simple graph grows in relation to the number of vertices.
Corollary 1.3
For any finite set V, there are 2^( |V| Choose 2 ) distinct simple graphs with vertex set V
To understand this, let’s consider an example. Suppose we have a set V with 3 elements: V = {A, B, C}. We want to find the number of distinct simple graphs that can be formed using these elements as vertices.
To form a graph, we consider all possible pairs of vertices. In this case, we have three vertices, so we can form three pairs: (A, B), (A, C), and (B, C). For each pair, we have two choices: either we include an edge between the two vertices or we don’t include an edge.
Since we have three pairs and two choices for each pair, we multiply the number of choices together: 2 * 2 * 2 = 8. Therefore, there are 8 distinct simple graphs that can be formed using the vertices A, B, and C.
The above image are the first two possible graphs from our example.
If this is still confusing don't worry! we will continue this in our next blog.
Conclusion
In this blog post we covered the basic definition of a graph, loops, multiple edges and simple graphs. I hope this helped you
What’s next
In the next chapter, we will delve deeper into simple graphs and other graph types as well as their representation. We will cover programmatic implementations. So subscribe to this blog and get ready to learn about the world of graph theory!
Stay tuned for regular updates, tips, and tutorials on all things graph-related! Feel free to connect, share your thoughts, and use the following hashtags to join the graph community: #GraphTheory #DataStructures #NetworkAnalysis #DataVisualization #GraphDatabases #AlgorithmDesign. 📲🔍
Image reference
