Graphs as networks of vertices and edges

Start with four rooms and three direct links

Four rooms are labelled A, B, C and D. A direct link joins A to B, another joins A to C, and a third joins B to C. There is no link touching D. Which rooms have a direct link to A? How many separate links have we described?

Draw one labelled dot for each room and one line for each listed link. A has two directly linked rooms, B and C. There are three links altogether. D still belongs to our room collection even though no line touches it. The drawing keeps the connection information and leaves out room sizes and link lengths.

Counting each object once and adding whole-number counts are the preparation. The linked representation lesson helps you compare a picture with its table. No graph theory is assumed. On a first reading, follow the room picture, edge table and degree count, then the two-ends proof. Return to matrices and arrows after those ideas feel secure.

Name the objects and the connections

A vertex is one object in the network, drawn as a labelled dot. Vertices is its plural. An edge is one connection between two endpoints. The finite collection of vertices is called V, and the finite collection of edges is called E. The notation |V| and |E| means the number of vertices and edges, respectively.

Two vertices are adjacent when an edge joins them directly. An edge is incident with a vertex when that vertex is an endpoint of the edge. In the room network, A and B are adjacent, and the A–B edge is incident with both A and B. D is isolated: no edge has D as an endpoint.

Undirected means the edge has no chosen direction: the A–B connection is the same edge as B–A. It does not assert anything about physical travel until the model says what a connection means. A link may instead represent friendship, a cable or an allowed comparison. Choose the meaning before interpreting the graph.

An edge has two endpoint occurrences, also called edge ends. They may be at two different vertices or, when a loop is permitted, at the same vertex twice. Our graphs are finite. We explicitly permit V to be empty; then E must also be empty because every edge needs declared endpoints. With nonempty V, an empty E simply leaves all vertices isolated.

Change the drawing without changing the network

Move A, B, C and D or bend the three room edges. If the vertex labels and each edge’s endpoints stay the same, the labelled network stays the same. An edge’s displayed length, a crossing and the area inside a triangle are not extra data in this unweighted graph.

In the crossing example, edges A–C and B–D cross without a vertex dot at the intersection. The model has four vertices and two edges. The crossing adds no connection between the edges. If you deliberately add a new vertex E there and replace the two edges by A–E, E–C, B–E and E–D, you have a different network with five vertices and four edges.

A line passing near a vertex is not incident with it unless that vertex is a declared endpoint. The endpoint table decides ambiguous pictures. Redrawing is a useful check: compare the complete endpoint lists, including isolated vertices, instead of judging shape alone.

Vertex names can also be changed consistently. A one-to-one matching between all vertices that preserves every edge and its multiplicity is a relabelling of the structure. Here we keep labels fixed when comparing drawings; merely having the same number of vertices and edges does not establish the same labelled network.

Say which kinds of edge the model allows

A simple undirected graph has no loops and no parallel edges. A loop joins a vertex to itself. Parallel edges are distinct edges with the same unordered pair of endpoints. In a simple graph, each edge can therefore be written as a two-element set, such as {A,B}; writing {B,A} describes that same edge.

Two different cables between A and B are two edges, even though their endpoints match. We give them identities e1 and e2 rather than storing {A,B} only once and losing one cable. More generally, an undirected multigraph here permits loops and parallel edges: each identified edge has two endpoints, with order ignored and repetition allowed.

For example, e1 and e2 join A to B, e3 joins B to C, and e4 is a loop at A. D is still declared and isolated. The graph has four vertices and four edges. The loop is one edge whose two ends are both at A; it is not two distinct edges.

Check the convention in other sources: some reserve multigraph for parallel edges and use pseudograph when loops are allowed. Here the explicit endpoint rules settle the meaning. Collapsing parallel edges to one or deleting loops changes the model; it cannot be done silently when counting connections.

Degree counts edge ends at a vertex

In an undirected graph, the degree deg(v) of a vertex v is the number of edge ends at v. Each ordinary edge contributes one to each endpoint’s degree. A loop contributes two to its single vertex’s degree, because both of its ends occur there. Every parallel edge contributes separately.

For the simple room graph, deg(A)=2, deg(B)=2, deg(C)=2 and deg(D)=0. In a simple graph, degree also equals the number of distinct neighbours. That shortcut fails for a multigraph: two parallel A–B edges give A two edge ends but only one distinct other neighbour.

For the four-edge multigraph, A receives one end from e1, one from e2 and two from its loop e4, so deg(A)=4. B receives one from each of e1, e2 and e3, so deg(B)=3. C has degree 1 and D has degree 0. The degrees add to 8. A has only the distinct neighbours A and B when we allow a vertex to be its own neighbour through a loop.

The incidence table places vertices in rows and identified edges in columns. An entry is the number of ends of that edge at that vertex: 0, 1 or 2. Every column sums to 2; every row sums to that vertex’s degree. This convention records loops without hiding either of their ends.

Prove the degree-sum formula by counting the same ends

For every finite undirected graph with the stated loop convention, the sum of all vertex degrees is 2|E|. The sum symbol Σ means add one term for every vertex, so Σ(v∈V)deg(v)=2|E|. The right side counts two endpoint occurrences for each edge.

To prove it, form one counting item for each edge together with a choice of its first or second end. Even a loop supplies two distinct occurrences attached to the same vertex. Counting by edges gives 2|E| items. Grouping those same items by their attached vertex gives deg(v) in the group for v. The groups do not overlap and include every item, so their total is the degree sum.

The proof works with parallel edges because they have different identities. It also works when there are no edges: every degree is 0 and both totals are 0. For V empty, the sum has no terms and is defined as 0, again matching |E|=0. Finiteness lets us use these ordinary whole-number totals.

The name handshaking lemma recalls people shaking hands: each handshake contributes one count at each of two people. An actual handshake model normally uses no self-handshakes; loops are a separate mathematical extension handled by the two-ends rule. The diagram verifies a small case, while the counting argument proves the formula for every finite case.

Use degree totals as checks, with their limits

The degree sum is even, because it is twice an integer. Even degrees contribute an even total; an odd degree contributes one leftover unit after pairing its other units. Thus the degree sum has the same even-or-odd status as the number of odd-degree vertices. That number must be even.

The four-edge multigraph has degrees 4,3,1,0 and exactly two odd-degree vertices. A single loop has degree 2 and no odd-degree vertex. A proposed undirected graph with degrees 2,2,1 would have odd sum 5, so no such graph exists under these conventions.

Even total is necessary, not sufficient for a proposed simple graph. On four vertices, degrees 3,3,1,1 sum to 8 and are each at most 3, yet they are impossible. Each degree-3 vertex must be adjacent to all other vertices; then each of the remaining vertices already has at least two neighbours, contradicting degree 1.

Nor do degrees identify the whole labelled network. The edges A–B and C–D give every vertex degree 1. The different edges A–C and B–D also give every vertex degree 1. Endpoint tables distinguish them. A degree total is a strong consistency check, not a replacement for the connection data.

Read an adjacency table with an explicit convention

For a simple undirected graph, an adjacency matrix is a square table with the same vertex labels in its rows and columns. Put 1 at row u, column v when u and v are adjacent, otherwise 0. Its diagonal entries are 0 because loops are excluded. It is symmetric: the entry for u,v equals the entry for v,u.

Each row sum is the corresponding degree. The room matrix has a 1 at A,B and another at B,A. Those two entries record the two ends of one undirected edge, not two edges. Therefore adding all entries gives 2|E|, and dividing that total by 2 gives the edge count.

For the multigraph tables in this lesson, we explicitly extend the convention: off the diagonal, entry u,v is the number of edges joining u and v; on the diagonal, entry v,v is twice the number of loops at v. This symmetric table still has degree as each row sum. A loop at A therefore gives diagonal entry 2, not 1.

Other matrix conventions put the number of loops itself on the diagonal. Under that convention, a plain row sum misses one contribution per loop. Read the rule before using a matrix formula. Our endpoint and incidence tables preserve individual edge identities; the adjacency counts alone preserve multiplicities but not the names e1 and e2.

Directed edges separate incoming and outgoing counts

A directed edge, also called an arc, has a chosen tail and head: A→B starts at tail A and ends at head B. The reverse B→A is a different directed connection. A model may have either one, both or neither. In our directed examples, identified parallel arcs and directed loops are allowed only when shown in the endpoint list.

The outdegree of v counts arcs whose tail is v. The indegree counts arcs whose head is v. A directed loop at v contributes 1 to each count. Parallel arcs contribute separately. A loop has one tail occurrence and one head occurrence even when both are at the same vertex.

For arcs A→B, A→C, B→C and C→B, A has outdegree 2 and indegree 0; B has outdegree 1 and indegree 2; C has outdegree 1 and indegree 2. The outgoing counts sum to 4, and the incoming counts also sum to 4, equal to the number of arcs.

In every finite directed graph, Σ outdegree(v)=|E| and Σ indegree(v)=|E|. Each arc is counted once by its unique tail and once by its unique head. Individual vertices need not have equal incoming and outgoing counts: A in our example is a counterexample. Adding both totals gives 2|E|, but each separate total is |E|.

The directed adjacency entry at row u, column v is the number of arcs u→v. Row sums give outdegrees and column sums give indegrees. This table need not be symmetric. A directed loop has diagonal entry 1 per loop, unlike our undirected double-loop convention. An arrow’s direction, not where its curved line sits, decides tail and head.

Predict, reveal and reconstruct the exact network

Choose a finite example. The picture and complete endpoint list are visible before revealing results. Predict each degree, or both directed counts; then show the exact degree, adjacency and incidence tables. The highlighted A vertex helps you trace edge ends, and dashed orange edges mark those incident with A. A loop at A must be traced twice for degree.

Compare the two room layouts: every connection and degree should agree. Compare the crossing with the added centre vertex: their tables differ because the endpoint data differs. Compare one directed loop with one undirected loop: the same number of edges produces different matrix diagonal conventions, with the corresponding correct counts.

Every explorer example is a complete finite graph, not a cropped piece of a larger network. The drawing is schematic and has no length scale. Its tables contain every declared vertex and edge, including zeros for isolated vertices. The proofs above cover finite graphs beyond these examples; visual inspection alone cannot prove a general theorem.

When you later study routes, cycles or trees, keep this first question: which connections are actually present, and do they have directions? Those topics add definitions to the vertex-and-edge model. They are not prerequisites for this lesson. Return here whenever an endpoint, a crossing or a degree count is unclear.

Worked examples

Try it yourself

1. In the room network, is A–B different from B–A? Is A–D present?

   Show the answer and reasoning

   A–B and B–A name the same undirected edge. A–D is absent.

   An undirected edge ignores endpoint order; the exact listed pairs are A–B, A–C and B–C.

2. A graph has vertices A,B,C and no edges. How many vertices, edges and odd-degree vertices does it have?

   Show the answer and reasoning

   Three vertices, zero edges and zero odd-degree vertices.

   Every declared vertex remains present, but all degrees are 0. Zero is even.

3. Under this lesson’s convention, what edges can a graph with V empty have? Verify the degree sum.

   Show the answer and reasoning

   It can have no edges; the degree sum and 2|E| are both 0.

   An edge needs declared endpoints, and an empty vertex collection supplies none. The empty sum is defined as 0.

4. One vertex A has two distinct undirected loops. Find |E|, deg(A) and the undirected adjacency entry.

   Show the answer and reasoning

   |E|=2, deg(A)=4 and the single adjacency entry is 4.

   Each loop is one edge with two ends at A. Our undirected matrix diagonal stores twice the number of loops.

5. Three separate undirected cables join A to B. What is deg(A), and how many distinct other neighbours does A have?

   Show the answer and reasoning

   Degree 3 and one distinct other neighbour, B.

   Every cable contributes a separate end, but all three use the same other vertex. Degree and neighbour count coincide only under the appropriate simple-graph condition.

6. The drawing of A–C and B–D crosses once, with no extra vertex at the intersection. Give the vertex and edge counts.

   Show the answer and reasoning

   Four vertices and two edges.

   A crossing does not create an endpoint. Replacing it with an explicit vertex E and four subdivided edges would describe another network.

7. Can an undirected graph have degrees 4,2,1,0? Explain using a general theorem.

   Show the answer and reasoning

   No; the degree sum is 7, which cannot equal twice an integer edge count.

   Equivalently, exactly one listed vertex has odd degree, contradicting the even number of odd-degree vertices.

8. An undirected graph has degrees 3,3,2,2,0. If such a graph exists, how many edges does it have? Does this computation alone establish existence?

   Show the answer and reasoning

   It must have five edges. The computation alone does not establish existence.

   The degree sum is 10, so |E|=10/2=5. The handshaking formula is a necessary constraint, not a general construction.

9. In a vertex-by-edge incidence table, an undirected loop at B has what entries in its column?

   Show the answer and reasoning

   Entry 2 in row B and 0 in all other rows.

   Both ends of that one edge occur at B. The column still sums to 2.

10. For an undirected multigraph on A,B, the adjacency matrix has rows (2,3) and (3,0). Interpret the loops, parallel edges, degrees and edge count.

    Show the answer and reasoning

    One loop at A, three A–B edges, degrees 5 and 3, and four edges altogether.

    The diagonal 2 means one loop. The off-diagonal 3 records three identified connections without their names. The degree sum 8 gives four edges.

11. A single vertex has one directed loop. Find its indegree, outdegree and directed adjacency entry.

    Show the answer and reasoning

    All three are 1.

    That arc supplies one head and one tail at the vertex. The directed diagonal counts loops once, unlike our undirected double-loop rule.

12. For arcs A→B and A→C only, list all incoming and outgoing counts. Must they be equal at each vertex?

    Show the answer and reasoning

    A:(0,2), B:(1,0), C:(1,0), with pairs written (indegree,outdegree). They need not be equal at a vertex.

    Both global totals equal 2, but A sends two and receives none. The theorem equates global totals, not each row’s individual counts.

13. Why do the degree lists alone fail to distinguish {A–B,C–D} from {A–C,B–D}?

    Show the answer and reasoning

    Both labelled networks have degrees 1,1,1,1, although their endpoint pairs differ.

    Degrees keep how many ends occur at each vertex and discard which other endpoints belong to those ends. Inspect the actual edge data.

14. Remove the A loop from the four-edge multigraph e1:A–B,e2:A–B,e3:B–C,e4:A–A. What changes?

    Show the answer and reasoning

    The edge count falls from 4 to 3. A’s degree falls from 4 to 2, while B,C,D keep degrees 3,1,0.

    Deleting a loop removes two ends at its vertex. The degree sum falls from 8 to 6, exactly twice the one-edge change.

What to carry forward

• A graph records declared vertices and connections; a drawing’s crossings and lengths add no endpoint data.
• For undirected degree, count edge ends: every loop contributes two and every parallel edge contributes separately.
• The undirected degree sum is twice the edge count, so the number of odd-degree vertices is even.
• A degree total is a consistency condition; it does not uniquely specify a network or prove every proposed degree list realizable.
• Directed arcs contribute once to an outgoing total and once to an incoming total. Matrix rules must state the direction and loop convention.