Count the vertices, edges and loops of a graph

Which rule counts the edges in a graph correctly?

Counting graph elements

A graph is made from labelled vertices and edges joining them. Count every edge line once, including loops and separate parallel edges

1. 1Count labelled points Each labelled point is one vertex \(\displaystyle A,B,C,D\;\Rightarrow\;v=4\)
2. 2Count each line once Each joining line contributes one to the edge count \(\displaystyle 5\text{ edge lines}\;\Rightarrow\;e=5\)
3. 3Count a loop once A loop contributes one edge, although both of its ends attach to the same vertex \(\displaystyle \text{one loop}\;\Rightarrow\;1\text{ edge}\)
4. 4Count parallel edges separately Two or more edges between the same pair of vertices are counted one at a time \(\displaystyle AB_1,\;AB_2\;\Rightarrow\;2\text{ edges}\)

Count the labelled vertices in this graph

Count every edge in the graph, including the loop and each parallel edge

Which line counts the edges correctly?

Describe the graph by lists

A finite undirected graph has a vertex list and an edge list. Each edge has an unordered pair of endpoints; equal endpoints give a loop. To preserve parallel copies, label the edges or repeat the pair in the list. Keep isolated D in the vertex list even though no edge mentions it

Which list describes all four edges of this graph without losing information?

Crossings and positions are not extra vertices

Moving a labelled vertex or bending an edge does not change the endpoint information. Two lines crossing on the page are not joined unless the drawing marks a vertex there. A graph diagram is not automatically a scale map, and a straight edge is not automatically shorter in the model

Choose vertices and edges to match the context

In a simple friendship model, vertices can be people and edges mutual friendships; a loop or duplicate friendship is normally excluded. In a component-connection model of an electrical circuit, vertices can be junctions and each edge a component between junctions, so parallel components remain separate. In a utility model, vertices can be supply and receiving sites with edges for proposed connections. State the chosen interpretation instead of assuming every graph allows the same features

Four kinds of graph problem

For a proposed network, an existence question asks whether a required network can be built at all. A construction question asks for an actual valid diagram. A counting question asks for the number of vertices, edges or valid arrangements. An optimisation question specifies an objective, such as least total cable length, and the constraints

A designer asks for a network satisfying a given edge list, and wants an actual drawing rather than only a yes/no answer. What type of task is this?

Draw from a list, ungraded

On paper, draw vertices P, Q, R and S. Use the edge list PQ, PR, PR, QQ, RS. Label the vertices and keep both PR edges and the loop at Q. Then state the numbers of vertices, edges and loops

Model: a diagram from the edge list

This is one valid drawing. Its geometry is not unique: the required information is one PQ edge, two PR edges, one loop QQ and one RS edge. There are four vertices, five edges and one loop. A differently positioned drawing with exactly those incidences is equally valid

Inspect this model drawing. Which feature represents the repeated PR pair in the edge list?