-
Regular
-
Complete
Graph Theory Playground
A graph is a set of dots, called vertices, joined by lines, called edges. Draw one here with a few clicks and the playground tells you what kind of graph it is: how many pieces it has, whether it is a tree, how few colours it needs, whether you can draw it in one stroke, and more. Click a property to see it on your graph, change an edge, and watch the answers change. Click an empty spot to add a vertex. Click a vertex, then another, to join them with an edge; do it again to remove the edge. Drag a vertex to move it. Switch the click to Erase and click a vertex or an edge to delete it. With a vertex selected, Delete removes it and Escape lets go. Click a property to show it on the graph. Example loads a well-known graph, Random graph makes one, Tidy up spreads the vertices out, and Complement joins exactly the pairs that were not joined. Ctrl+Z undoes a step.
How it works
- Click an empty spot to add a vertex. Click a vertex, then another, to join them; do it again to remove the edge. Drag a vertex to move it.
- Read the properties under the graph, and click one to show it: a colouring, the two sides, an Euler trail, a spanning tree, the shortest cycle or the diameter.
- Load an example such as the Petersen graph, make a random graph, take the complement, or switch the click to Erase to delete vertices and edges.
What the properties mean
The degree of a vertex is the number of edges at it. A graph is connected when every vertex can reach every other along the edges, and a tree when it is connected and has no cycle. It is bipartite when its vertices split into two sides with every edge going across, which happens exactly when it has no cycle of odd length. The chromatic number is the fewest colours that give neighbours different colours. The shortest cycle is called the girth, and the diameter is the largest distance between two vertices, counted in edges.
Drawing in one stroke
An Euler trail uses every edge exactly once. Leonhard Euler saw in 1736, with the seven bridges of Königsberg, what stands in the way: every time a trail passes through a vertex it uses two of its edges. So either every degree is even, and the trail can end where it started, or exactly two degrees are odd, and the trail must run from one of them to the other. Carl Hierholzer later proved that this, with all edges in one piece, is also enough. Load the house example and find where the stroke has to start.
Frequently asked questions
What is a graph in graph theory?
A set of points, called vertices or nodes, and lines between some pairs of them, called edges. It is not a chart of a function: it describes only what is joined to what. Road maps, social networks, molecules and computer networks are all graphs.
How is the chromatic number worked out?
The playground tries to colour the graph with one colour, then two, then three and so on, and for each number it searches all the ways that matter, always colouring next the vertex whose neighbours already use the most colours. The first number that works is the chromatic number. For the graphs you can draw here that takes a moment at most; on a very hard graph the search stops early and the value is shown as an upper bound.
When does a graph have an Euler path?
When all of its edges are in one piece and no more than two vertices have an odd degree. With no odd vertices there is an Euler circuit that ends where it starts; with two, every Euler path starts at one of them and ends at the other. The number of odd vertices is always even, so it is never exactly one.
What is the complement of a graph?
The graph on the same vertices whose edges are exactly the pairs that were not joined before. The complement of the complement is the graph you started with. The Petersen graph's complement, for example, is 6-regular, because each vertex was joined to 3 of the other 9.
Why is the Petersen graph famous?
It is a small graph with 10 vertices and 15 edges that is a counterexample to many hopeful guesses. Every vertex has degree 3, its shortest cycle has length 5, any two vertices are at most 2 edges apart, and it cannot be drawn without edges crossing. The playground starts with it.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor