Undirected graph

An undirected graph is a graph where each edge has no direction, so the connection between two vertices works both ways. In Combinatorics, it is the standard way to model mutual relationships and network structure.

What is undirected graph?

An undirected graph is a combinatorics object made of vertices and edges, where each edge connects two vertices without pointing from one to the other. If vertex A is connected to vertex B, then B is connected to A in exactly the same way. That is the main feature that separates it from a directed graph.

Think of it as a network where the relationship is two-way. A friendship network is the classic example, because if two people are friends, the connection is mutual. In graph notation, you can draw the edge as a simple line with no arrowheads. The line just says the two vertices are linked.

This matters because a lot of graph theory in Combinatorics starts with this simpler setup. Once direction is removed, you focus on structure instead of flow, so questions usually become about degree, connectivity, cycles, paths, and how the graph breaks into components. You may be asked whether a graph is connected, how many edges touch a vertex, or whether there is a route between two points.

A common detail is degree. In an undirected graph, the degree of a vertex is the number of edges incident to it. If one edge touches a vertex, that contributes 1 to the degree, even though the edge works both ways. That is different from directed graphs, where you separate incoming and outgoing edges.

Undirected graphs can still be simple or more complicated. They can contain cycles, which are closed walks that return to the starting vertex, and they can also include special cases like isolated vertices with degree 0 or leaf vertices with degree 1. In shortest path problems, you often treat each edge as a two-way connection and look for the route with the fewest steps or least weight between vertices.

Why undirected graph matters in COMBINATORICS

Undirected graphs are the starting point for a lot of Combinatorics problems, especially ones about networks and paths. If you can read an undirected graph correctly, you can answer questions about whether a graph is connected, how many components it has, and whether a route exists between two vertices. Those skills show up again when you study algorithms and optimization.

They also give you a clean setting for graph properties. Degree counts, cycles, isolated vertices, and leaf vertices are easier to interpret when no arrows are involved. That makes undirected graphs a good place to practice graph vocabulary before moving to more complex models.

This term also connects directly to shortest path work. Many path problems assume the graph is undirected, so every edge can be used in either direction unless the problem says otherwise. If you mix up direction, you can get the wrong path count or miss a valid route entirely.

Beyond problem solving, undirected graphs are how you model mutual relationships in a precise way. That includes friendship networks, two-way roads, and any system where the connection is symmetric. When you see a graph question in Combinatorics, this is often the first decision you make: are the edges one-way or two-way?

How undirected graph connects across the course

Vertex

Vertices are the points in the graph, so an undirected graph is built from them. When you count degree or trace a path, you are always moving from one vertex to another through edges. A lot of graph questions start by identifying the vertices first, then checking how they are connected.

Edge

An edge is the connection between two vertices, and in an undirected graph that connection has no arrow. This means the same edge can be read in either direction. If a problem asks for degree, connectivity, or a path, you are really analyzing how the edges join the vertices.

Connected Graph

A connected graph is one where every vertex can be reached from every other vertex through paths. Undirected graphs are often used when the question is whether a network stays in one piece or breaks into separate parts. If a graph is not connected, you may need to identify its components.

Floyd-Warshall Algorithm

Floyd-Warshall is a shortest path algorithm that works on weighted graphs, including many undirected ones. When the graph has no direction, the algorithm treats each edge as available in both directions if the problem allows it. That makes the graph’s symmetry important when you set up the distance table.

Is undirected graph on the COMBINATORICS exam?

A problem set question might give you a network and ask you to identify whether it is directed or undirected, then use that choice to answer path, degree, or connectivity questions. The first move is to check for arrowheads. No arrows means the edge works both ways, so you count degree by the number of incident edges and look for routes without worrying about direction.

If the question is about shortest paths, you treat each edge as usable in either direction unless the problem says the graph is weighted or restricted. If it is about components, you trace which vertices are reachable from each other. On quizzes, a common trap is reading an undirected graph as if it had one-way flow, which can make you miss valid paths or miscount degrees.

Undirected graph vs directed graph

These are easy to mix up because both use vertices and edges, but a directed graph has arrows that show one-way movement. In an undirected graph, the connection is symmetric, so you can travel across an edge in either direction. That difference changes degree counts, path choices, and how you interpret reachability.

Key things to remember about undirected graph

• An undirected graph is a graph where each edge connects two vertices without an arrow, so the relationship goes both ways.

• In Combinatorics, undirected graphs are used for mutual relationships, network structure, and path questions.

• The degree of a vertex in an undirected graph is the number of edges touching it.

• Undirected graphs can have cycles, connected components, isolated vertices, and leaf vertices.

• Always check for direction before solving a graph problem, because a missing arrow changes how you count and trace paths.

Frequently asked questions about undirected graph

What is an undirected graph in Combinatorics?

It is a graph whose edges have no direction, so each edge represents a two-way connection between vertices. In Combinatorics, this setup is used for networks where the relationship is symmetric, like mutual friendship or two-way travel. You usually read the graph by checking which vertices are connected and how many edges touch each vertex.

How do you tell if a graph is undirected?

Look for arrows on the edges. If the edges are plain lines with no arrowheads, the graph is undirected. That means the connection can be followed in either direction, which changes how you find paths and count degree.

What is the difference between an undirected graph and a directed graph?

An undirected graph has no arrows, so every edge works both ways. A directed graph has arrows, so each edge points from one vertex to another in a specific direction. This affects reachability, degree, and shortest path reasoning, so the distinction matters a lot on graph problems.

Where do undirected graphs show up in shortest path problems?

They show up whenever a path can move across an edge in either direction, such as a two-way road or an unrestricted connection network. For shortest path questions, you trace allowed routes between vertices and compare the path lengths or weights. If the graph is undirected, you do not treat an edge as one-way unless the problem says otherwise.