Worked solution: graph with edges AB, BC, CD, DA, AC

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

Graph theory Answer checked
Answer
4 vertices, 5 edges; degrees A=3, B=2, C=3, D=2; connected\text{4 vertices, 5 edges; degrees A=3, B=2, C=3, D=2; 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?
    Yes, every vertex can be reached from every other.
  6. Euler trails and circuits
    Euler trail exists (not a circuit): exactly two odd vertices, A and C, so start at one and end at the other.
  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