Balanced Graph in Mathematics: Meanings and Examples

Charts & pivot tables · Updated November 22, 2026

A balanced graph does not have one universal meaning across mathematics: the definition depends on the area and the author. In elementary graph theory, the phrase often points to a bipartite graph whose two vertex sets have the same size; in signed graph theory, it means a graph in which every cycle has a positive sign. Checking which definition a source uses is essential, because these properties are different.

Why the term has more than one meaning

A graph is made of vertices and edges, but extra structure or a particular question can change what it means for that graph to be balanced. An ordinary graph has no signs on its edges, while a signed graph assigns each edge a positive or negative sign. Similarly, the word balanced may refer to the sizes of the two sides of a bipartition, or to a balance between incoming and outgoing edges in a directed graph.

For that reason, the safest approach is to look for a definition near the first use of the term. If a text discusses bipartite graphs, matchings, or two vertex classes, it may mean equal-sized sides. If it discusses positive and negative edges or signed cycles, it means balance in signed graph theory. If it discusses directed edges and degrees, it may mean equal indegree and outdegree at each vertex.

In many introductory settings, authors use balanced bipartite graph when they specifically mean a bipartite graph with equal-sized parts. Some sources shorten this to balanced graph, but that shorthand is not reliable without context.

Bipartite graphs and their two parts

A graph is bipartite if its vertices can be divided into two disjoint sets, often called X and Y, so that every edge has one endpoint in X and the other in Y. There are no edges joining two vertices within X or two vertices within Y. The two sets form a bipartition of the graph.

A basic theorem gives a useful way to recognize this structure: a graph is bipartite if and only if it has no cycle of odd length. For example, a triangle is not bipartite, because its three vertices form an odd cycle. A square is bipartite: alternate vertices can be placed in X and Y so every edge crosses between the sets.

When the two sets have equal numbers of vertices, the bipartite graph is called balanced bipartite. If the sizes are different, it is still bipartite, but it is not balanced in this equal-part sense. The word balanced here refers to the number of vertices on each side, not to how many edges each side touches.

What equal-sized parts do and do not imply

Suppose a bipartite graph has parts X and Y. It is balanced by the equal-part definition when |X| = |Y|. This condition concerns the number of vertices, not their degrees, the number of edges, or whether every vertex has a partner.

  • A complete bipartite graph K3,3 has three vertices in each part, with every possible cross-edge present. It is balanced bipartite.
  • A star K1,3 has one center in one part and three leaves in the other. It is bipartite but its parts are unequal, so it is not balanced under the equal-part definition.
  • A cycle with four vertices is balanced bipartite: its alternating parts each contain two vertices.
  • A graph with two vertices in each part can be balanced even if it has only one edge. Equal part sizes do not require a dense or regular graph.

Equal part sizes are necessary for a perfect matching, meaning a set of edges that pairs every vertex with exactly one other vertex. They are not sufficient. A balanced bipartite graph can still have an isolated vertex, for example, and then no perfect matching exists. Hall’s marriage theorem gives the exact criterion: every subset S of X must have at least |S| neighbors in Y. In practical terms, no group on one side can collectively be connected to too few possible partners on the other.

Examples that make the distinction clear

Consider a square whose vertices are arranged around a cycle. Put the first and third vertices in X and the second and fourth in Y. Each edge crosses between X and Y, and both sets contain two vertices. The square is therefore bipartite and balanced bipartite. It also has a perfect matching: choose either pair of opposite edges.

Now consider a three-leaf star. Put its center in X and its leaves in Y. All edges cross between the parts, so the graph is bipartite. But the part sizes are one and three. It cannot have a perfect matching, since one center cannot be matched separately to all three leaves. This example shows why bipartite and balanced bipartite are not interchangeable terms.

For a more subtle example, take two vertices in X and two in Y, but connect both X vertices only to the same single vertex in Y. The graph has equal-sized parts, so it meets the equal-part definition of balanced bipartite, but Hall’s condition fails for the two vertices in X. It has no perfect matching. Balance of the part sizes is a simple numerical property; a perfect matching is a stronger structural property.

Balance in signed graph theory

A signed graph is an ordinary graph in which every edge is marked positive or negative. In this setting, a signed graph is balanced if every cycle contains an even number of negative edges. Equivalently, the product of the edge signs around every cycle is positive. A cycle with an odd number of negative edges is called a negative cycle and makes the signed graph unbalanced.

For example, a triangle whose three edges are positive is balanced. A triangle with exactly one negative edge is unbalanced, because that cycle has one negative edge. A triangle with two negative edges is balanced: its cycle has an even number of negative edges, and the product of its signs is positive.

This definition is not about the number of vertices in two parts. One useful equivalent description is that a signed graph is balanced exactly when its vertices can be assigned to two groups so that positive edges lie within groups and negative edges run between groups. The groups may have different sizes. Another equivalent test is that it is possible to switch signs at vertices so that every edge becomes positive. Switching flips the signs of all edges incident to a selected vertex; it does not change whether the signed graph is balanced.

How to identify the intended definition

When a problem uses the words balanced graph, first identify what information the graph carries and what property is being tested. These clues usually reveal the intended meaning:

  • If the graph is split into two vertex classes and the question compares their sizes, look for the equal-sized bipartite definition.
  • If edges carry positive and negative labels and cycles are discussed, use the signed-graph definition.
  • If the graph is directed and the discussion compares incoming and outgoing edges at each vertex, the intended property may be a balanced digraph: every vertex has equal indegree and outdegree.
  • If a theorem or assignment defines balanced explicitly, use that definition even if another branch of mathematics uses the same phrase differently.

For the equal-part version, test bipartiteness first, then count the vertices in each part. A breadth-first search or depth-first search can assign alternating sides; a conflict indicates an odd cycle and hence a non-bipartite graph. For signed balance, inspect cycle signs or use an equivalent structural test rather than comparing the sizes of vertex sets.

Related terms that are easy to confuse

A balanced bipartite graph is not necessarily a regular graph. A regular graph has the same degree at every vertex; equal part sizes say nothing about equal degrees. For instance, K3,3 is 3-regular, but a balanced bipartite graph can have vertices of quite different degrees.

Balanced is also not the same as complete. A complete bipartite graph has every possible edge between its two parts. K2,5 is complete bipartite but its parts are not equal, while a graph with two vertices in each part and only one edge is balanced bipartite but far from complete.

Nor does a balanced graph necessarily have a perfect matching, as the examples above show. Equal-sized sides make such a matching possible in principle, but the arrangement of edges must also allow all vertices to be paired. Similarly, signed balance is not a claim that positive and negative edges occur in equal numbers; it is a condition on every cycle.

Why graph balance matters

Balanced bipartite graphs arise naturally in assignment and pairing problems. One part might represent workers and the other jobs, or students and projects. Equal numbers on each side are relevant if every item must be paired, but Hall’s condition determines whether the available choices actually permit a complete assignment. This distinction prevents a common mistake: treating equal totals as proof that a complete matching exists.

Signed graphs model relationships that can be friendly or antagonistic, consistent or conflicting, depending on the application. A balanced signed graph has no cycle whose signs create a contradiction: around every closed route, the number of negative relationships is even. This idea is useful when studying whether local positive and negative labels can be explained by a consistent division of vertices into groups.

In directed networks, equal indegree and outdegree at every vertex is important for routes that use each directed edge once. Such graphs are often called balanced digraphs, and the degree condition is related to Euler circuits. This is another reason not to infer a definition from the word alone: the graph’s direction, labels, and surrounding topic matter.

Frequently Asked Questions

Is every bipartite graph balanced?
No. Bipartite means that vertices can be divided into two sets with every edge crossing between them. Under the equal-part meaning of balanced bipartite, the two sets must also have the same number of vertices.

Does a balanced bipartite graph always have a perfect matching?
No. Equal part sizes are necessary, but the edges must connect the vertices in a way that satisfies Hall’s condition. An isolated vertex or a group with too few neighbors can prevent a perfect matching.

How can I tell whether a graph is bipartite?
Try assigning vertices to two sets so every edge joins opposite sets. This can be done by alternating assignments while traversing each connected component. A conflict means the graph contains an odd cycle and is not bipartite.

What makes a signed graph balanced?
Every cycle must have an even number of negative edges, or equivalently a positive product of signs. One negative cycle is enough to make the signed graph unbalanced.

Does balanced mean that both sides have the same number of edges?
Not in the usual equal-part definition. It means the two vertex classes have equal sizes. Edge counts or vertex degrees may differ, and signed-graph balance is defined by cycle signs instead.

Related

Try it: the Percentage Formula Generator: percent of, percent change, increase and decrease, with the formula.

More in Charts & pivot tables

Sources: Function behaviour and menu paths: Microsoft Support documentation for Excel. Method & sources

Spotted an error in this guide? Let us know.