Graph Theory Definition Types of Graphs Formulas Properties and Solved Examples
The concept of graph theory in maths plays a key role in mathematics and is widely applicable to real-life situations like networking, transport, and computer science, as well as exam problem-solving for board exams and competitive tests like JEE.
What Is Graph Theory in Maths?
A graph in mathematics is a collection of points, called vertices (or nodes), connected by lines, called edges. The study of these objects—their relationships, types, and applications—is called graph theory in maths. You’ll find this concept applied in areas such as network analysis, computer programming, and operations research.
Key Formula for Graph Theory in Maths
Here’s the standard formula used often in graph theory:
Degree Sum Formula: \( \sum \text{deg}(v) = 2 \times E \)
Where \( \text{deg}(v) \) is the degree of vertex \( v \) and \( E \) is the number of edges.
Euler’s Formula (for planar graphs): \( V - E + F = 2 \)
Where \( V \) = vertices, \( E \) = edges, \( F \) = faces.
Key Terminology Explained
| Term | Meaning |
|---|---|
| Vertex (Node) | A point in the graph where edges meet |
| Edge (Link) | A line connecting two vertices |
| Degree | The number of edges attached to a vertex |
| Directed Graph | Edges have direction (arrows); also called digraph |
| Undirected Graph | Edges have no direction (simple lines) |
| Complete Graph | Every pair of vertices is connected |
| Cycle | A path that starts and ends at the same vertex, with no repeats |
| Tree | A connected graph with no cycles |
Cross-Disciplinary Usage
Graph theory in maths is not only useful in Maths but also plays an important role in Physics, Computer Science, and even social sciences. Whether you are drawing networks, planning routes, or analysing data, these concepts are essential for advanced studies and competitive exams.
Types of Graphs with Examples
- Simple Graph: No loops, no multiple edges.
- Complete Graph: Each node connects to every other node.
- Directed Graph: Edges have arrows showing direction.
- Weighted Graph: Each edge has a value (weight) assigned.
- Tree: A kind where there's exactly one path between any two vertices.
- Cyclic Graph: Contains at least one cycle.
For visual learners, you can think of Facebook's friend network as an undirected graph, while Twitter followership is modeled as a directed graph. Explore more real-case diagrams here.
Step-by-Step Illustration: Sample Problem
Question: In a simple graph with 4 vertices and 5 edges, what is the sum of degrees of all vertices?
1. The degree sum formula says: Sum of degrees = \( 2 \times \) (Number of edges)2. Substitute: \( 2 \times 5 = 10 \)
3. Final Answer: The sum of degrees = 10.
Get more worked examples and exam-level practice here.
Speed Trick or Vedic Shortcut
A quick tip: To identify if a given graph is Eulerian (a path/circuit covering every edge exactly once), check if all vertices have even degrees. If so, the graph has an Eulerian circuit! These checks save precious minutes in board and JEE exams.
Learn more about Euler's Theorem in graph theory for exam shortcuts.
Applications in Real Life
- Network design (Internet, social media connections)
- Transport and route planning
- Project scheduling (PERT networks, Gantt charts)
- Biology (food webs, neural networks)
- Computer Science (search algorithms, database design)
Try These Yourself
- Draw a graph with 3 vertices and 2 edges.
- Is a tree always a connected graph? Why?
- List all types of graphs you know and give 1 example of each.
- Check if the following degree sequence is possible: 2, 2, 2, 2.
Frequent Errors and Misunderstandings
- Confusing between directed and undirected edges.
- Miscounting degrees (remember: loops count as two in degree calculation).
- Not checking if a path repeats edges when solving for Euler circuits.
Relation to Other Concepts
The idea of graph theory in maths connects closely with discrete mathematics, set theory, and logic. Mastering graphs will boost your problem-solving in many advanced maths topics, including algorithms and computer networks.
Classroom Tip
A great way to remember: "Vertices are dots, edges are lines. A cycle means you can start and end at the same point without retracing steps." Vedantu’s teachers often use color-coded sketches to help visualize graph questions for quick understanding.
We explored graph theory in maths—from definition, formula, examples, speed checks, and applications to connections with other topics. Practice regularly with Vedantu’s quizzes and worksheets to become confident and quick at solving graph-based problems in any exam or real-life scenario.
Recommended next steps:
- Types of Graphs in Maths
- Euler’s Theorem Explained
- Set Theory Symbols (for graph notation)
- Discrete Mathematics Overview
FAQs on Graph Theory Concepts Properties and Applications in Mathematics
1. What is graph theory in mathematics?
Graph theory is a branch of mathematics that studies graphs, which are structures made of vertices (nodes) connected by edges (links). In graph theory, a graph is usually written as G = (V, E), where:
- V is the set of vertices.
- E is the set of edges connecting pairs of vertices.
2. What is the difference between a simple graph and a multigraph?
The main difference is that a simple graph has no multiple edges or loops, while a multigraph can have multiple edges between the same pair of vertices. In detail:
- A simple graph has at most one edge between any two vertices and no edge from a vertex to itself.
- A multigraph may have more than one edge between the same two vertices.
3. What is the degree of a vertex in graph theory?
The degree of a vertex is the number of edges incident to that vertex. It is usually denoted by deg(v). Key points:
- Each edge connected to the vertex counts as 1.
- A loop counts as 2 toward the degree.
- In a directed graph, we distinguish between in-degree and out-degree.
4. What is the Handshaking Lemma?
The Handshaking Lemma states that the sum of the degrees of all vertices in a graph equals 2|E|, where |E| is the number of edges. In formula form:
- ∑ deg(v) = 2|E|
5. What is a complete graph?
A complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. A complete graph with n vertices is denoted by Kn. The number of edges in Kn is:
- n(n − 1) / 2
6. What is the difference between a path and a cycle in graph theory?
A path is a sequence of vertices connected by edges with no repeated vertices, while a cycle is a path that starts and ends at the same vertex. Specifically:
- A path of length k has k edges and k+1 distinct vertices.
- A cycle has at least 3 vertices and forms a closed loop.
7. What is a connected graph?
A connected graph is a graph in which there is a path between every pair of vertices. This means:
- For any vertices u and v, at least one path connects them.
- The graph has a single connected component.
8. What is a tree in graph theory?
A tree is a connected graph with no cycles. Key properties of a tree with n vertices include:
- It has exactly n − 1 edges.
- There is exactly one simple path between any two vertices.
9. What is an Eulerian path and Eulerian circuit?
An Eulerian path is a path that uses every edge exactly once, and an Eulerian circuit is an Eulerian path that starts and ends at the same vertex. Conditions for a connected graph:
- An Eulerian circuit exists if every vertex has even degree.
- An Eulerian path (but not circuit) exists if exactly two vertices have odd degree.
10. What is a Hamiltonian path and Hamiltonian cycle?
A Hamiltonian path is a path that visits every vertex exactly once, and a Hamiltonian cycle is a Hamiltonian path that returns to the starting vertex. Important points:
- It focuses on visiting vertices, not edges.
- There is no simple necessary and sufficient condition like Eulerian graphs.
