Choosing Vertices, Edges, And Weights

Start with the Question

A graph model is useful when its structure records the information needed to answer a question. The first decision is therefore not which graph to draw, but what the question asks. Are we asking which appointments overlap, whether a direct service exists, how often one person contacts another, or what kinds of bonds join atoms? Each question may require a different choice of vertices, edges, direction and weights, even when the underlying data describe the same system.

Unless stated otherwise, a graph is finite and simple: its edges are undirected, with no loops or multiple edges. For directed data, we use a directed graph whose edges are arcs, written \(\overrightarrow{uv}\) from \(u\) to \(v\). A weighted graph includes a function assigning a specified value, or weight, to each edge or arc. A weight is meaningful only after its interpretation and units have been stated.

Definition: An encoding of a real-world system specifies what its vertices represent, what relation makes two vertices adjacent (or gives an arc from one to the other), and what additional information—such as weights, labels or times—is retained. A question is preserved by an encoding if the encoded data contain enough information to determine the correct answer to that question.

Two checks help make this precise. First, every graph object should represent the intended real-world object: a vertex should not ambiguously represent a person in one place and an event in another. Second, test whether the encoding can distinguish situations that give different answers. If it cannot, the graph by itself is not a reliable answer to that question.

Pairwise Relations and Edges

For a symmetric pairwise relation, an undirected edge is a natural encoding. For example, let the vertices be appointments and join two vertices when the corresponding appointments cannot both be accepted. The edge then records a conflict, not a shared appointment or an actual sequence of events. A vertex set with no edges between its members represents a collection with no pairwise conflicts.

Theorem: Let \(X\) be a finite set and let \(R\) be a symmetric, irreflexive relation on \(X\). Form a simple graph with vertex set \(X\), joining distinct \(x,y\) exactly when \(xRy\). A subset \(S\subseteq X\) has every pair related by \(R\) if and only if \(S\) is a clique. It has no pair related by \(R\) if and only if \(S\) is an independent set.

Proof. A clique is, by definition, a set of vertices in which every two distinct vertices are adjacent. In the constructed graph, \(x\) and \(y\) are adjacent exactly when \(xRy\). Thus every pair of distinct elements of \(S\) is related exactly when \(S\) is a clique. An independent set is, by definition, a set with no adjacent pair. Using the same edge rule, that holds exactly when no pair of distinct elements of \(S\) is related by \(R\). If \(S\) has zero or one element, both pairwise conditions hold because there are no pairs of distinct elements to check; it is both a clique and an independent set under these definitions. \(\square\)

Worked Example: Appointments That Share a Room

Four appointments use the same room. Their time intervals are \(A=[9,10)\), \(B=[9.5,10.5)\), \(C=[10,11)\), and \(D=[11,12)\), with time measured in hours. The half-open convention means an appointment ending at a time and one starting at that same time do not overlap. Make one vertex per appointment, and join two vertices exactly when their intervals overlap.

For intervals \([s_1,e_1)\) and \([s_2,e_2)\), overlap occurs exactly when \(\max(s_1,s_2)<\min(e_1,e_2)\). For \(A,B\), the two sides are \(\max(9,9.5)=9.5\) and \(\min(10,10.5)=10\), so they overlap. For \(A,C\), they are \(\max(9,10)=10\) and \(\min(10,11)=10\); the strict inequality fails, so they do not overlap. For \(A,D\), they are \(11\) and \(10\), so they do not overlap. For \(B,C\), they are \(10\) and \(10.5\), so they overlap. For \(B,D\), they are \(11\) and \(10.5\), so they do not overlap. For \(C,D\), they are \(11\) and \(11\), so they do not overlap.

Therefore \(V=\{A,B,C,D\}\) and \(E=\{AB,BC\}\). Appointments \(A,C,D\) can all be accepted together: none of the three pairs is an edge. This check concerns only pairwise room conflicts in the stated intervals; it does not assign appointments to different rooms or account for any unrecorded constraint.

Check: the edge set has two entries, matching the two overlapping pairs found in the six-pair calculation. The selected set \(\{A,C,D\}\) contains no edge of \(E\), as required.

When Direction and Weights Matter

If a relationship can hold in one direction but not the other, an undirected edge loses a distinction. In a transport network, a road may be one-way; in a communication record, one person may send a message without receiving one in return. Use an arc \(\overrightarrow{uv}\) when the relation goes from \(u\) to \(v\). A weight can record a quantity such as distance, time or number of interactions, but these meanings are not interchangeable.

Worked Example: Direct Services Between Stations

Consider stations \(V=\{A,B,C,D\}\). The available direct services and their distances in kilometres are \(A\to B:4\), \(B\to C:3\), \(A\to C:10\), \(C\to D:2\), \(B\to D:9\), and \(D\to A:7\). Represent the system by a directed weighted graph: each station is a vertex, each direct service is an arc, and its distance is the arc weight.

The arc set is \(\{\overrightarrow{AB},\overrightarrow{BC},\overrightarrow{AC},\overrightarrow{CD},\overrightarrow{BD},\overrightarrow{DA}\}\). The weight function assigns \(4,3,10,2,9,7\) kilometres to those arcs in the same order. There are six listed arcs. The question “Is there a direct service from \(A\) to \(C\)?” has answer yes, and the weight on that arc gives its distance as \(10\) km.

This encoding also answers whether a direct service exists from \(C\) to \(A\): it does not, because \(\overrightarrow{CA}\) is not in the arc set. If we replace every arc by an undirected edge, the edge \(AC\) would incorrectly suggest a direct connection in both directions. If we keep the directed arcs but discard weights, we can still answer whether a direct service exists, but not its stated distance. The model preserves the direct-service questions and distances on listed services; it does not, by itself, answer questions about the best multi-service journey.

Check: the six weights sum to \(4+3+10+2+9+7=35\) km across all listed services, but this sum is only a check on the data entered. It is not a journey distance: the six arcs are separate services, not one continuous trip.

For social data, direction and weights can encode different facts. An arc may represent a message sent, while a weight may represent the number of messages during a specified period. If the question concerns whether any message was sent, one may use an arc for each positive count. If the question concerns how many messages were sent, the count must also be retained.

Worked Example: Message Counts in a Week

Suppose a record for users \(P,Q,R,S\) gives these positive message counts during one week: \(P\) sent \(3\) messages to \(Q\), \(Q\) sent \(1\) to \(P\), \(Q\) sent \(2\) to \(R\), and \(S\) sent \(1\) to \(Q\). Use a directed weighted graph, with each user as a vertex, an arc for each positive count, and the count as its weight.

Here \(V=\{P,Q,R,S\}\), \(E=\{\overrightarrow{PQ},\overrightarrow{QP},\overrightarrow{QR},\overrightarrow{SQ}\}\), and the corresponding weights are \(3,1,2,1\). The question “Did \(Q\) send a message to \(P\)?” is answered by the arc \(\overrightarrow{QP}\), and the count is \(1\). The reverse arc \(\overrightarrow{PQ}\) has weight \(3\), so replacing the two arcs by one undirected edge would erase the difference between the two directions.

Adding the outgoing counts gives \(3+1+2+1=7\) messages in total. By sender, \(P\) has \(3\), \(Q\) has \(1+2=3\), \(R\) has \(0\), and \(S\) has \(1\); these totals give \(3+3+0+1=7\). A graph that records only whether an arc exists can answer which directed pairs exchanged messages, but cannot recover these counts. The weekly graph also does not preserve the order or timestamps of the messages.

Check: the four positive arc weights sum to \(3+1+2+1=7\), agreeing with the sum \(3+3+0+1=7\) of the sender totals.

What an Encoding Can Recover

The following criterion formalizes the test for lost information. Treat the complete encoded object as including every feature the model retains: vertices, edges or arcs, weights, labels and any other recorded attributes. If vertex names have no meaning for the question, compare encodings up to a relabeling that preserves all those attributes.

Theorem: Let \(D\) be a set of possible real-world situations, \(F\) an encoding that assigns each situation an encoded graph, and \(q\) a question whose answer is specified for each situation. The answer to \(q\) can be recovered from \(F(x)\) for every \(x\in D\) if and only if \(F(x)=F(y)\) implies \(q(x)=q(y)\) for all \(x,y\in D\).

Proof. Suppose first that the answer can be recovered from the encoding. Then there is a rule that takes \(F(x)\) as input and returns \(q(x)\). If \(F(x)=F(y)\), that rule receives the same input in both cases, so it must return the same answer. Hence \(q(x)=q(y)\). Conversely, suppose that equal encodings always have equal answers. For any encoding \(z\) that occurs as \(F(x)\), define its recovered answer to be \(q(x)\). This definition is unambiguous: if also \(F(y)=z\), then \(F(x)=F(y)\), so the assumption gives \(q(x)=q(y)\). Thus the rule “return \(q(x)\) for any situation encoded as \(z\)” recovers the answer from the encoding. Encodings outside the image of \(F\) need no answer because they represent no situation in \(D\). \(\square\)

In practice, this theorem asks a useful question: could two different systems produce exactly the same recorded graph even though the answer you need differs? If so, the model needs more information. A directed graph without timestamps cannot answer a question about the order of events. An unweighted graph cannot distinguish a connection costing \(2\) from one costing \(20\). A simple graph cannot distinguish one bond from several bonds between the same pair unless extra labels or weights are added.

Worked Example: A Molecular Skeleton and Bond Types

Consider a molecule with two hydrogen atoms \(H_1,H_2\) and two carbon atoms \(C_1,C_2\), with a single bond from \(H_1\) to \(C_1\), a triple bond between \(C_1\) and \(C_2\), and a single bond from \(C_2\) to \(H_2\). Its simple underlying graph has \(V=\{H_1,C_1,C_2,H_2\}\) and \(E=\{H_1C_1,C_1C_2,C_2H_2\}\).

This graph preserves the connectivity pattern: it records which atom pairs are bonded. But the same simple graph would result if the \(C_1C_2\) bond were single rather than triple. Therefore the unlabelled graph cannot answer “What is the bond order between the carbon atoms?” Add a bond-order label, with values \(1,3,1\) on the three edges, to preserve that information. The vertices also need atom-type labels if the question concerns which vertices are carbon or hydrogen.

Check: the graph has four vertices and three distinct edges, regardless of the bond-order labels. The labels distinguish the bond data without creating extra vertices or parallel edges.

A Practical Model Check

Before using a graph, write down the question it must answer and check each modeling choice against it. A compact checklist is:

Vertices: What entities or events are represented? Are they all included, and is each one represented exactly as intended?
Edges: What specific relation makes two vertices adjacent? Is the relation symmetric, or should an arc have a direction?
Weights and labels: Which quantities or types must be retained? State units, time periods and what a zero or missing value means.
Information loss: What distinctions does the encoding discard? Could that loss change the answer to the stated question?

A common mistake is to treat an edge as a generic sign that “something is connected” and then use it to answer a more specific question. In the transport example, the wrong undirected calculation would see the service \(A\to C\), replace it by edge \(AC\), and conclude that a direct service \(C\to A\) exists. That conclusion does not follow: the original list contains \(\overrightarrow{AC}\), not \(\overrightarrow{CA}\). Keeping direction corrects the answer. Likewise, dropping the weight \(10\) from \(\overrightarrow{AC}\) may preserve whether the service exists, but it cannot preserve its distance.

Choosing a graph is therefore a matter of matching the representation to the question, not of making a system look graph-like. The same entities may support several valid encodings, each useful for different questions. A careful model states what it records, checks that the answer is determined by that information, and avoids drawing conclusions about data it has discarded.

Check Your Understanding

For each question, identify what the graph must record and name one distinction that could be lost by a simpler encoding.

A set of appointments uses shared equipment. What should vertices and edges represent if the question is which appointments can be accepted together?
A delivery service has one-way links with distances. What information is lost by replacing its directed weighted graph with an unweighted undirected graph?
A communication record asks both whether a message was sent and how many were sent. What should arcs and weights represent?
Why does a simple molecular graph need labels or weights to distinguish single and triple bonds between the same atoms?
State the condition in the recoverability theorem that lets an answer be determined from an encoding, and explain what failure of that condition means.