Use degrees, adjacency lists, and matrices to inspect the same relation.
By the end: check edge counts and explain when a representation preserves or loses information.
The degree of a vertex is the number of incident edges. In our simple undirected graphs, it is also the number of its neighbors. An isolated vertex has degree zero. Summing all degrees counts each edge twice, once at each endpoint. The sum therefore equals twice the edge count.
This gives a useful impossibility test. The number of odd-degree vertices must be even, because an odd number of odd contributions would make the total odd. An even degree sum is necessary but not sufficient for a proposed simple graph to exist. Three vertices cannot each have degree four when loops and parallel edges are forbidden.
Use the fixed undirected graph with vertices A through F and edges AB, AC, BC, BD, CE, DE, EF. To count the degree of C, inspect which edge records contain C. They are AC, BC, and CE, so C has degree 3. The edge DE does not count for C, even if its line passes near C in a particular drawing. An edge is incident on a vertex when that vertex is one of its recorded endpoints. Counting endpoint occurrences rather than nearby strokes makes the result independent of the layout and of accidental line crossings.
Imagine making two small marks for each edge, one beside each endpoint name. AB adds one mark to A and one to B. AC adds another to A and one to C. Continuing through the seven records gives degrees 2, 3, 3, 2, 3, 1 in alphabetical order. Summing those values counts fourteen marks. This is the reason the degree sum is twice the number of edges, rather than an empirical pattern noticed in one picture. Every permitted undirected edge has two distinct endpoints, and the counting procedure includes each endpoint exactly once.
Parity means whether a whole number is even or odd. Adding an even number does not change the parity of a running total. Adding an odd number changes it. For the final degree sum to be even, the number of odd contributions must therefore be even. In the fixed graph the odd-degree vertices are B, C, E, and F, four vertices altogether. They need not be paired by edges with each other. This is a statement about the sum of endpoint counts, not a rule that every odd-degree vertex must have an odd-degree neighbor.
The parity test can reject a report without reconstructing the graph, but passing it does not construct a graph. Consider a claimed simple graph on exactly four vertices A, B, C, D with degrees 3, 3, 1, 1 respectively. The sum is 8, so the edge count would have to be 4. Each degree is at most 3, the number of other vertices. Nevertheless the report is impossible. A degree of 3 forces A to connect to B, C, and D. B's degree of 3 forces B to connect to A, C, and D.
Those forced edges already give C two different neighbors, A and B, and give D the same two neighbors. Their degrees cannot then be 1. No placement of the vertices can repair that contradiction. Compare a possible four-vertex report with degrees 3, 2, 2, 1. Edges AB, AC, AD, and BC realize it: A touches three edges, B and C each touch two, and D touches one. Both reports have the same degree sum and implied edge count. Their difference appears only when the endpoint requirements are checked together, rather than one vertex at a time.
The simple-graph assumptions are doing work in these arguments. Without loops, one vertex cannot connect to itself. Without parallel edges, it cannot count several distinct edges to the same neighbor. Consequently its degree cannot exceed the number of other vertices. A physical system with several separate connections between the same pair of sites would require a different record if those connections must be counted separately. In this lesson, count the edges of the stated simple graph. Do not silently interpret its degree as a count of cables, trains, or customers unless one edge truly represents one such object.
An adjacency list records the neighbors of each vertex. Undirected edges appear in two lists. An adjacency matrix has one row and one column per vertex; a one means the corresponding edge exists and a zero means it does not. The matrix of an undirected graph is symmetric across its diagonal.
A directed matrix uses rows as sources and columns as destinations here. Row sums give outdegrees; column sums give indegrees. Summed outdegrees and summed indegrees each equal the edge count, rather than twice that count. A weighted matrix needs a separate absence marker if a real edge may have weight zero.
A representation preserves a graph when it lets us recover the intended vertices and edges without guessing. For the fixed graph, start with A's neighbor list B, C. This gives edges AB and AC. B's list A, C, D repeats AB and adds BC and BD. C's list A, B, E repeats AC and BC and adds CE. D lists B, E; E lists C, D, F; F lists E. Retaining only the first occurrence of each unordered pair recovers exactly seven edges. The lists repeat information deliberately because either endpoint may be the starting point of a query.
A matrix expresses the same information with positions instead of variable-length lists. Give every vertex a row and a column, ordered A through F. Put 1 at row B, column D because BD exists, and put 0 at row B, column E because BE does not exist. Since this graph is undirected, row D, column B must also contain 1. The diagonal cells are 0 because loops are excluded. Reading all six cells of C's row finds the three ones under A, B, and E. Their column labels recover C's neighbor list rather than merely its degree.
| From / to | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 | 0 |
| B | 1 | 0 | 1 | 1 | 0 | 0 |
| C | 1 | 1 | 0 | 0 | 1 | 0 |
| D | 0 | 1 | 0 | 0 | 1 | 0 |
| E | 0 | 0 | 1 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 0 | 1 | 0 |
Recovering undirected edges from the full matrix requires avoiding double counting. Each off-diagonal 1 has a reflected partner on the other side of the diagonal. Read only cells where the row's letter precedes the column's letter, such as B before D. That half contains seven ones in the fixed example, one for each edge. Summing all rows instead gives fourteen ones because both endpoint incidences are present. These are two correct counting procedures for different quantities. A report of fourteen edges would confuse the full matrix's duplicated incidences with distinct undirected edge records.
Direction removes that reflected-cell requirement. For a separate graph with vertices A, B, C, D and directed edges A to B, A to C, B to C, C to D, use rows for origins and columns for destinations. Row A has two ones and column A has none. Row C has one one, under D, while column C has two ones, from A and B. Thus C has one outgoing edge and two incoming edges. Each arrow occupies just one cell, so the matrix contains four ones altogether. There is no obligation for row B, column A to match row A, column B.
For weighted records, decide whether the cells store existence or value. Suppose the directed vertex set is A, B, C, with edges A to B of cost 0 and B to C of cost 2, and no other edges. An existence matrix puts 1 in both occupied cells and keeps the costs elsewhere. A cost matrix can instead put 0 and 2 in those cells, but must use a distinct absence mark in the others. Filling all absent cells with numerical zero would erase the distinction between a free permitted move and a move that does not exist.
| From / to | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 1 | 0 |
| C | 0 | 0 | 0 | 1 |
| D | 0 | 0 | 0 | 0 |
The row and column names are part of the representation. Reordering them together can preserve the graph, just as moving labeled vertices can preserve a drawing. Reordering rows while leaving their labels unchanged generally does not. When two matrices look different, first compare their labeling conventions and then their endpoint facts. Likewise, a neighbor list ordered C, B describes the same undirected neighbors as B, C. List order may later affect which tied choice a procedure makes, but it does not add or remove an edge. A representation's incidental order and the represented relation must remain separate.
6 vertices; 7 edges.
| From / to | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 | 0 |
| B | 1 | 0 | 1 | 1 | 0 | 0 |
| C | 1 | 1 | 0 | 0 | 1 | 0 |
| D | 0 | 1 | 0 | 0 | 1 | 0 |
| E | 0 | 0 | 1 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 0 | 1 | 0 |
| Vertex | Neighbor list | Degree |
|---|---|---|
| A | B, C | 2 |
| B | A, C, D | 3 |
| C | A, B, E | 3 |
| D | B, E | 2 |
| E | C, D, F | 3 |
| F | E | 1 |
Each edge has two ends. This is a count, not a probability.
| Quantity in the displayed undirected graph | Value |
|---|---|
| Vertices | 6 |
| Edges | 7 |
| Degrees A through F | 2, 3, 3, 2, 3, 1 |
| Degree sum | 14 = twice 7 |
Select Seven-edge network in the model above and focus on E. Its neighbor list is C, D, F, so its degree is 3. In the matrix, E's row has ones under those same three letters. In the drawing, exactly CE, DE, and EF end at E. These are not three independent measurements of the physical world. They are three representations computed from one supplied edge record. Agreement checks that you are interpreting the representations consistently. It cannot establish that the original record contains every real service or that all its services are currently usable.
Work backward from the matrix to check the total. The six row sums are 2, 3, 3, 2, 3, and 1. Their sum is 14, so the edge count must be half of 14, or 7. Now recover the edges from the half above the diagonal: AB, AC, BC, BD, CE, DE, EF. This second route to the count identifies the actual pairs, which a sum alone cannot do. If one edge had been replaced by a different edge, the total might remain seven while the recovered endpoint set would change.
Next select Three-edge star. This replaces the graph with vertices A, B, C, D and edges AB, AC, AD. The center A has degree 3. Each other vertex has degree 1, giving a degree sum of 6 and an edge count of 3. All four vertices have odd degree, which is allowed because four is even. Compare the matrix's first row with the other rows. The first row contains three ones, while each other row has only the entry under A. A single high-degree center does not require high degrees at its neighbors.
Finally select Four isolated vertices. There are still four objects in the model, but the edge set is empty. Every neighbor list is empty, every degree is zero, and all sixteen matrix cells are zero. The degree sum is zero, which equals twice the zero edge count. This is not a missing or failed display. It is a valid graph representing four objects with no recorded pairwise relation. The vertex names and the matrix dimensions retain information that would disappear if we represented the graph by an unlabeled empty edge list alone.
A useful paper comparison changes only one record rather than replacing a preset. Start again with the six-vertex graph and remove BC while retaining all six vertices and the other six edges. B and C each lose one incident edge, so their degrees become 2 and 2. Every other degree stays fixed, producing 2, 2, 2, 2, 3, 1. The new degree sum is 12, exactly two below 14. In a matrix this deletion clears row B, column C and row C, column B. One undirected edge edit changes two cells and two endpoint counts.
| From / to | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 |
The available presets are complete replacements, not a general graph editor. The BC deletion is an explained calculation, not another promised control. Keeping that distinction also clarifies what the exploration establishes. Each preset illustrates the same endpoint-count rule with a different distribution of degrees, including the empty edge set. None tests every possible graph. The general rule follows from the two ends of every undirected edge; the presets make its consequences visible. If a displayed count disagreed, that would indicate a representation or counting error, not an exception to the rule under the stated assumptions.
With n vertices, a full matrix reserves n squared entries even when few edges exist. An adjacency-list representation stores vertices plus edge incidences, using space proportional to n plus the edge count. A matrix offers a direct edge lookup; a basic list may require scanning the source vertex's neighbors. These are representation tradeoffs, not claims about measured runtime here.
Degree is local. A highly connected vertex can sit in a small isolated component, while a low-degree bridge endpoint connects two large regions. Degree alone does not establish influence, reliability, shortest distance, or causality. First ask what the recorded connections mean and which paths they permit.
For six vertices, a full adjacency matrix reserves six rows of six cells, or 36 cells, whether the graph has seven edges or none. A neighbor-list description needs the six vertex identities and fourteen neighbor entries for the seven-edge undirected graph. It repeats each edge at its two endpoints. These counts compare logical entries, not bytes in a particular program. A cell, a name, and a list container need not use equal memory. The counts explain why a mostly empty relation can leave many unused matrix positions without establishing measured storage or speed for this visualizer.
Different questions favor different access patterns. To ask whether B connects directly to E, a matrix reader goes to one named cell. A basic neighbor-list reader inspects B's entries A, C, D and finds no E. To ask for all B's neighbors, that list already provides exactly three names. A matrix reader instead checks all six positions in row B. This is the mechanism behind the lookup tradeoff. The comparison concerns the described reading procedures. It does not show how many machine instructions the page uses, or how long either representation takes on a real device.
| Graph | Edges | Full matrix cells | Neighbor entries |
|---|---|---|---|
| Base AB, AC, BC, BD, CE, DE, EF | 7 | 36 | 14 |
| Every pair among A through F | 15 | 36 | 30 |
Lists become less compact relative to a matrix as the graph fills. With the same six vertices, an undirected simple graph can contain every possible pair, fifteen edges. Each vertex would then list the other five, giving thirty neighbor entries. The matrix still has 36 cells, of which thirty are off-diagonal ones and six are diagonal zeros. Fifteen comes from six possible first endpoints times five different second endpoints, divided by two because this counts each unordered pair twice. This maximum uses the simple-graph assumptions and does not describe the seven-edge preset's actual edge count.
Degree counts are a more lossy description than either full representation. Consider two separate undirected graphs on vertices A through F. The first has edges AB, BC, CD, DE, EF, FA, forming a six-vertex cycle. The second has edges AB, BC, CA, DE, EF, FD, forming two separate triangles. Every vertex has degree 2 in both graphs, and both have six edges. In the cycle, A can reach F directly and can also reach D through B and C. In the two-triangle graph, no journey from A can reach D, E, or F.
The degree list cannot distinguish those graphs because it records how many neighbors each vertex has but discards which neighbors they are. Even retaining the alphabetical degree sequence does not restore the missing pair identities in this example. A neighbor list or matrix does distinguish them. A's neighbors are B and F in the cycle, but B and C in the triangle graph. This is why replacing a graph by a degree chart can invalidate a reachability argument. Summaries can be correct and useful while omitting exactly the structure needed for a different question about the same objects.
The same caution applies when checking data quality. Suppose a station report gives the right degree at every vertex. That agreement does not prove it gives the right edge set, as the two degree-2 examples demonstrate. Agreement on edge count is even weaker. To validate a representation against source records, compare vertex identities, direction where applicable, and endpoint pairs, then compare any attached values in their stated units. Such a check establishes faithful transcription of those records. It still leaves open whether the records are complete, current, and appropriate for the intended journey or network decision.
A simple undirected graph is reported to have degrees 3, 3, 2, 1, 0. Can this be correct?
Sum them before trying to draw it.
| Contribution | Running sum |
|---|---|
| 3 | 3 |
| 3 | 6 |
| 2 | 8 |
| 1 | 9 |
| 0 | 9 |
No. The sum is 9, but twice an integer edge count is even. There are also three odd-degree vertices, which is impossible. A corrected even sum would still need a realizability check.
There are edges A to B, A to C, and B to C. What are the outdegree and indegree of C? Does C having two incoming edges permit travel from C to A?
A destination column is not an outgoing row.
| Vertex | Outdegree | Indegree |
|---|---|---|
| A | 2 | 0 |
| B | 1 | 1 |
| C | 0 | 2 |
C has outdegree 0 and indegree 2. It has no outgoing edge, so no directed route from C to A exists. Incoming edges describe arrivals, not permissions to depart.
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Graph representations, degree, trees, BFS and DFS. This course explicitly reserves path for a walk without repeated vertices; the reference uses a different path convention.
Directed reachability, strong components, DAGs, and topological orders. The lesson uses zero-indegree removal rather than the reference implementation's reverse-postorder method.