What is an Undirected Graph?

S3-SA5-0230

Grade Level:

Class 10

AI/ML, Data Science, Physics, Economics, Cryptography, Computer Science, Engineering

Definition

What is it?

An Undirected Graph is a collection of points (called 'vertices' or 'nodes') connected by lines (called 'edges'). In an undirected graph, the connections (edges) do not have a specific direction. This means if vertex A is connected to vertex B, then B is also connected to A in the same way.

Simple Example

Quick Example

Imagine your group of friends on WhatsApp. If you are friends with Rohan, Rohan is also friends with you. The 'friendship' connection doesn't go only one way. Here, each friend is a vertex, and each friendship is an edge, making it an undirected graph.

Worked Example

Step-by-Step

Let's create an undirected graph showing connections between four cities: Delhi, Mumbai, Chennai, and Kolkata.

STEP 1: Identify the vertices (cities). We have V = {Delhi, Mumbai, Chennai, Kolkata}.
---STEP 2: Identify the edges (direct flights/trains) between them. Let's say there are direct connections:
Delhi to Mumbai
Mumbai to Chennai
Chennai to Kolkata
Kolkata to Delhi
---STEP 3: Represent these connections as pairs of vertices. Since it's undirected, (Delhi, Mumbai) is the same as (Mumbai, Delhi).
E = {(Delhi, Mumbai), (Mumbai, Chennai), (Chennai, Kolkata), (Kolkata, Delhi)}
---STEP 4: Draw the graph. Draw four points for the cities. Draw a line connecting Delhi and Mumbai, another for Mumbai and Chennai, and so on. No arrows are needed on the lines because the connection is two-way.
---ANSWER: The resulting diagram with four points and four connecting lines (without arrows) is an undirected graph.

Why It Matters

Undirected graphs are super important in understanding how things are connected, from social networks to computer networks. They are used by engineers to design circuits, by data scientists to analyze relationships in data, and even in AI to model how different parts of a system interact. Learning this helps you think like a problem-solver in many advanced fields!

Common Mistakes

MISTAKE: Thinking an edge from A to B is different from B to A in an undirected graph. | CORRECTION: In an undirected graph, an edge (A, B) is exactly the same as (B, A). The connection is always two-way.

MISTAKE: Confusing vertices with edges. | CORRECTION: Vertices are the 'points' or 'nodes' (like cities or people), and edges are the 'lines' or 'connections' between them (like roads or friendships).

MISTAKE: Assuming all vertices must be connected to every other vertex. | CORRECTION: A graph can have some vertices connected and some not. There can also be isolated vertices with no edges.

Practice Questions

Try It Yourself

QUESTION: If a graph has 3 vertices (A, B, C) and edges (A, B) and (B, C), how many distinct edges are there? | ANSWER: 2 distinct edges.

QUESTION: Draw an undirected graph with 4 vertices (P, Q, R, S) and edges (P, Q), (Q, R), (R, P). What shape does it form? | ANSWER: A triangle.

QUESTION: In a group of 5 friends (Alia, Bharat, Chitra, Dev, Esha), Alia is friends with Bharat and Chitra. Bharat is friends with Alia and Dev. Chitra is friends with Alia and Esha. Dev is friends with Bharat. Esha is friends with Chitra. How many edges are there in the undirected graph representing their friendships? | ANSWER: 5 edges. (Alia-Bharat, Alia-Chitra, Bharat-Dev, Chitra-Esha, and remember Alia-Bharat is the same as Bharat-Alia, etc.)

MCQ

Quick Quiz

Which of the following describes an undirected graph?

Edges always have a specific direction.

Connections between points are always one-way.

Edges do not have a specific direction.

It can only have 3 vertices.

The Correct Answer Is:

In an undirected graph, the edges represent two-way connections without any specific direction. Options A and B describe directed graphs, and option D is incorrect as graphs can have any number of vertices.

Real World Connection

In the Real World

Think about how your mobile network connects different towers. If your phone can connect to Tower A, and Tower A can connect to Tower B, these connections are usually undirected. This helps engineers at companies like Jio or Airtel design networks efficiently, ensuring calls and data flow smoothly between users across cities.

Key Vocabulary

Key Terms

VERTEX: A point or node in a graph | EDGE: A line connecting two vertices | GRAPH: A collection of vertices and edges | UNDIRECTED: Having no specific direction for the connections

What's Next

What to Learn Next

Great job understanding undirected graphs! Next, you should explore 'Directed Graphs'. This will show you how connections can have a specific one-way path, which is crucial for understanding things like traffic flow or website links.