Worked solution: graph with edges AB, BC, CA, DE

Step-by-step working for this graph theory problem, produced and checked by the solver.

Graph theory Answer checked
Answer
5 vertices, 4 edges; degrees A=2, B=2, C=2, D=1, E=1; not connected\text{5 vertices, 4 edges; degrees A=2, B=2, C=2, D=1, E=1; not connected}
  1. Vertices and edges
  2. Degree of each vertex (number of edges meeting there)
  3. Adjacency matrix
  4. Handshaking lemma
    The degrees always add up to twice the number of edges.
  5. Connected?
    No, the graph splits into separate parts.
  6. Euler trails and circuits
    No Euler trail: the graph is not connected.
  7. Check: the row sums of the adjacency matrix equal the degrees

Change the numbers and solve your own

The method in brief

  1. List the vertices and count the degree of each.
  2. Handshaking lemma: the degrees add up to twice the number of edges.
  3. A graph is connected if you can get from any vertex to any other.
  4. Euler circuit: connected and all degrees even.

Full guide: Vertices, degrees, connectivity and Euler trails.

More Further maths examples on this topic