Combinatorics

Network board

Draw a graph; check connected, bipartite, Euler path.

For checking your work after you’ve tried it yourself.

Step 1:
Draw a network

Click to add points, then join them, or start from a preset.

Step 2:
Read the checks

Degrees, connected, two-colourable and Euler trail.

Step 3:
See why

Each check shows how to work it out by hand.
What it does.
A board for drawing networks of points and edges and checking their properties: every point's degree, whether it's connected, whether it can be two-coloured, and whether one trail can use every edge exactly once.
When it helps.
Checking a property you worked out for a network you drew on paper.
What it won’t do.
It checks the network you draw; it doesn't search for networks with a property.
Example.
The Königsberg bridges have four points of odd degree, so no walk crosses every bridge exactly once.
Start from

Click empty space to add a point. Drag points to move them.

Click to add points, or start from a preset

Checks

  • Points and edges0 points, 0 edges

    Degrees, largest first: none.

    Check it by hand

    Count the edges touching each point. Add the degrees: you should get twice the number of edges, because every edge has two ends. Here 0 = 0 = 2 × 0.

  • Connected?–
    Check it by hand

    Start at point 1 and tick it. Tick every neighbour of a ticked point, and repeat until nothing new gets ticked. If every point is ticked, it’s connected; otherwise start again from an unticked point to find the next piece.

  • Two-colourable (bipartite)?–
    Check it by hand

    Colour point 1 gold, its neighbours cyan, their neighbours gold, and so on. If two neighbours ever need the same colour, follow both back: you’ve found a cycle of odd length, and no two-colouring exists. If you finish with no clash, it’s bipartite.

  • Euler trail (every edge once)?–

    0 points with odd degree.

    Check it by hand

    Count the points with odd degree. Every time a trail passes through a point it uses two edges there, so only the start and end can have odd degree. 0 odd points: a closed trail exists (if all the edges are connected). 2 odd points: a trail exists from one to the other. More than 2: impossible.