Adjacent vertices are two vertices in a graph that share an edge. In Combinatorics, that relationship matters most in graph coloring, because adjacent vertices cannot have the same color.
Adjacent vertices are vertices in a graph that are connected directly by an edge. If you can trace a single line from one vertex to the other, those two vertices are adjacent. If there is no edge between them, they are not adjacent, even if they are close in a drawing.
In Combinatorics, this term shows up in graph theory, especially when you study how a graph is built and how its vertices interact. Adjacency is not about distance on the page. A graph can be drawn in many different ways, but adjacency stays the same as long as the edges stay the same.
The idea becomes most useful in vertex coloring. A proper coloring requires that adjacent vertices get different colors, so every edge creates a restriction. The more adjacency a graph has, the more limits you face when trying to color it with few colors.
Here is a simple example. Suppose vertices A, B, and C form a triangle. Then A is adjacent to B and C, B is adjacent to A and C, and C is adjacent to A and B. Because every pair is adjacent, all three vertices need different colors, so the graph needs at least 3 colors.
That is why adjacency is one of the first things you check before coloring a graph or finding its chromatic number. A graph with fewer edges usually has fewer adjacency restrictions, which can make it easier to color. A bipartite graph is a good contrast: its vertices can be split into two groups so every edge goes across the split, meaning adjacent vertices always land in different parts.
A common mistake is to think two vertices are adjacent just because they sit near each other in a picture. In graph theory, only the edge matters. The picture can change, but adjacency does not.
Adjacent vertices are the rule that drives vertex coloring in Combinatorics. Every time two vertices are adjacent, they force a color conflict, so adjacency tells you where the restrictions are before you even start coloring.
That makes this term useful for reading graphs quickly. If you can spot which vertices share edges, you can predict whether a graph will need many colors or only a few. A dense graph, with lots of adjacent pairs, tends to push the chromatic number up because there are more places where colors cannot repeat.
Adjacency also helps you connect graph drawings to graph properties. A messy sketch can hide the structure, but the adjacency pattern tells you the real problem. That is especially useful when a homework problem gives you a graph and asks whether it is bipartite, whether a greedy coloring works, or how many colors might be needed.
This concept also sets up bigger ideas in graph theory, like bounds on the chromatic number and the behavior of special graph families. Before you can use theorems about coloring, you need to know which vertices are adjacent and how those adjacencies interact across the graph.
Keep studying COMBINATORICS Unit 12
Visual cheatsheet
view galleryGraph
A graph is the whole structure that contains vertices and edges. Adjacent vertices are just one local relationship inside that structure, so you need the graph itself before adjacency even makes sense. When you study a graph, you are often really studying its adjacency pattern, because that pattern controls paths, cycles, coloring, and other properties.
Vertex Coloring
Vertex coloring uses adjacency directly. The rule is that any two adjacent vertices must have different colors, so every edge adds a constraint. If you can identify all adjacent pairs, you can check whether a coloring is valid and fix conflicts when two connected vertices accidentally share a color.
Chromatic Number
The chromatic number is the smallest number of colors needed for a proper vertex coloring. It depends on adjacency because every edge creates a mismatch requirement. More adjacency often means a larger chromatic number, although the exact value can be harder to find than just spotting the edges.
greedy coloring algorithm
A greedy coloring algorithm colors vertices one at a time using the first available color. It looks at which already-colored vertices are adjacent to the current one, then avoids those colors. The order you choose can change the result, which is why adjacency checks are built into every step.
A graph-coloring problem usually asks you to identify which vertices are adjacent before you assign colors. You might be given a drawing, an adjacency list, or an adjacency matrix and asked to decide whether a coloring is valid. The move is simple: check every edge, make sure its endpoints do not share a color, and explain any conflict in terms of adjacency.
If the question asks for the chromatic number or a lower bound, you often look for clusters of mutually adjacent vertices, like triangles, because they force more colors. On quizzes and problem sets, the most common mistake is missing an edge or treating non-adjacent vertices as if they had a restriction. If you read the adjacency pattern correctly, the rest of the coloring problem gets much easier.
Adjacent vertices are two vertices connected directly by an edge in a graph.
Adjacency does not depend on where the vertices are drawn, only on whether an edge joins them.
In vertex coloring, adjacent vertices must have different colors.
More adjacency usually means more coloring restrictions and often a larger chromatic number.
A bipartite graph has no adjacent vertices within the same part of the split.
Adjacent vertices are two vertices in a graph that share an edge. In Combinatorics, that idea matters because adjacency tells you which vertices cannot receive the same color in a proper coloring. It is a local graph relationship, but it affects the whole coloring problem.
Check whether there is an edge directly connecting them. If yes, they are adjacent; if no, they are not. The placement of the vertices in the drawing does not matter, so a close-looking pair is not automatically adjacent.
That is the rule of proper vertex coloring. An edge means the two endpoints are in conflict, so giving them the same color would violate the coloring condition. Every adjacent pair creates one more restriction you have to satisfy.
The chromatic number is the minimum number of colors needed to color a graph so adjacent vertices never share a color. More adjacency usually means more constraints, which can raise the chromatic number. A triangle is a quick example because all three vertices are pairwise adjacent, so it needs three colors.