Can an undirected graph have weights?

Yes. A weight can represent distance, strength or another explicitly defined quantity.

Can it contain a cycle?

Yes. In the worked example, A - B - C - A forms a cycle.

Is it the same as an undirected probabilistic graphical model?

No. That is a specialized use in which graph structure has a defined relationship to probability and conditional independence.

AI Glossary / Graphs and symbolic AI / Beginner

Undirected graph

Definition

An undirected graph is a collection of nodes joined by edges that have no orientation. An edge connecting A and B represents the same connection as an edge connecting B and A. It is useful when the relationship being modeled is symmetric.

What it means

Nodes represent things such as people, places, documents or components. Edges represent a chosen relationship between pairs of those things. In an undirected graph, that relationship does not have a source and destination.

For example, two documents sharing a topic can be connected symmetrically. By contrast, one document citing another is directional: the second need not cite the first. Choosing the graph type therefore encodes an assumption about the relationship, not merely a preference for drawing lines without arrows.

An undirected graph can have weights, labels, disconnected groups and cycles. Undirected does not mean unweighted, fully connected or random. Whether self-loops and repeated edges are allowed depends on the particular graph definition or software class.

How it works

An edge in a simple undirected graph can be treated as an unordered pair of different nodes. A neighbor list records each node's connected neighbors. If A lists B, B also lists A. An adjacency matrix for such a graph is symmetric: the entry for A,B matches the entry for B,A.

A path follows edges between nodes. Connectivity algorithms can find groups in which every node is reachable from every other. A node's degree counts its incident edges, with a self-loop counted twice under the usual convention.

A weighted undirected edge has one associated weight for that pair. If traveling from A to B and from B to A requires different costs, one shared undirected weight cannot preserve both values. A directed representation, or a more carefully specified model, is needed.

Three practical examples

A collaboration map links researchers who have jointly authored a paper, with an edge weight recording the number of shared papers.
A product network links items meeting a symmetric similarity rule, helping analysts inspect clusters.
A building map represents genuinely two-way corridors between rooms, subject to the chosen accessibility assumptions.

Think of it this way

Think of a line joining two pins on a noticeboard. The line says the pins are connected; it has no arrow telling you that the relationship runs from one pin to the other.

The line does not explain what the relationship means. A physical corridor, shared interest and statistical association can all be drawn this way, but they support different conclusions. The graph's definition supplies that meaning.

Worked example

Counting connections without double-counting

Create an invented graph with nodes A, B, C, D and E, and edges AB, AC, BC and CD. A has degree two, B degree two, C degree three, D degree one and E degree zero.

The sum of degrees is 2 + 2 + 3 + 1 + 0 = 8. Every edge contributes once at each endpoint, so dividing by two gives four edges. Counting both AB and BA as separate edges would be wrong for this simple undirected graph.

There are two connected components: {A, B, C, D} and {E}. A shortest unweighted path from A to D is A - C - D, with two edges. A - B - C - D also reaches D but uses three. This calculation uses edge count; different weights could change which path is cheapest.

Illustrative case study

The fictional MapleResearch team builds a network of co-authored reports. Its initial import contains both A - B and B - A records for some pairs. The analysts define the relationship as undirected and consolidate those records before counting collaborations.

They keep citation data in a separate directed graph because citing is not necessarily reciprocal. They also distinguish an isolated researcher from a researcher missing from the dataset, rather than assuming both mean no collaboration.

The invented case illustrates how the graph definition affects interpretation. No network centrality score is presented as a direct measure of a person's quality or importance.

Common misconceptions and mistakes

Undirected means every pair is connected. Many undirected graphs contain missing edges or separate components.
An undirected edge proves a two-way causal influence. Its meaning comes from the model; association alone does not establish causation.
All undirected graphs prohibit loops and multiple edges. Simple graphs do, while other undirected graph types may allow them.

Business use

Undirected graphs support analysis of relationships that are appropriately symmetric: shared projects, compatible components, physical adjacency and some similarity networks. They can help identify clusters, disconnected areas or connections whose removal separates a network.

Define the node identity, edge meaning, time window and weighting rule before interpreting results. Check whether the source data really supports symmetry. Converting a directional network to an undirected one can be useful for a particular question, but it discards information. A purchasing relationship and a mutual partnership should not become indistinguishable simply because an undirected layout looks cleaner.

Check your understanding

A follows B online, but B does not follow A. Does one undirected edge preserve that information?

Answer: No. It can record that some relationship exists, but it loses which person follows the other. Directed edges preserve the asymmetry.

Related terms

Node
Directed graph
Weighted graph
Cycle
Markov random field
edge
adjacency matrix
degree
connected component

Learn next

Read directed graphs and connected components. Draw a small network twice, once preserving direction and once removing it, and list which questions can no longer be answered after the conversion.

Sources

NetworkX developers, Graph class documentation, including undirected edges, attributes and the distinction from multigraphs: https://networkx.org/documentation/stable/reference/classes/graph.html

The official class description and examples were read. Its allowance for self-loops is a software-class convention, not the definition of every simple graph. The five-node calculation and fictional research example are original; no dataset analysis was performed.

Previous: Undersampling Next: Unembedding