Simple Graphs
Drag nodes to rearrange the graph. Add a new node by double clicking the plane.
Click a node to select. Clicking another node will draw a new edge, clicking the same node will remove it and any incident edges. Click the background to unselect a node.
Double click an edge to remove it.
Hover over a node to view its distance from all other nodes.

Show Degree   Color Components
on Nodes

Order (number of nodes):
Size (number of edges):
Degree vector: [ 3, 3, 3, 3 ]
Components: Yes
Regular: Yes
Eulerian: Yes
Number Spanning Trees: 2
About Simple Graphs
A simple graph is an undirected graph with no loops or multiple (parallel) edges.

Matrices
The adjacency matrix \(A\) of a simple graph on \(n\) nodes will be an \(n\times n\) real, symmetric matrix. The \(i\)th row and \(i\) column of the matrix is associated with node \(n_i\). The \((i,j)\)th entry of the matrix will be a 1 if nodes \(n_i\) and \(n_j\) are adjacent (connected by a single edge) and a 0 otherwise. Since simple graphs do not include loops, the diagonal entries of this matrix will always be 0.

The degree matrix \(D\) of a simple graph on \(n\) nodes will be an \(n\times n\) diagonal matrix. The \((i,i)\)th entry of this matrix will be the degree of node \(n_i\).

The Laplacian matrix \(L\) of a simple graph on \(n\) nodes will be an \(n\times n\) symmetric matrix. It is defined as the difference between the the degree and adjacency matrices, \(L = D-A\). The eigenvalues of this matrix have particular importance, and can be used to determine information about the connectedness of the graph. By Kirchoff's theorem, we can determine the number of spanning trees in the graph using these eigenvalues as well.

Connected Components
A connected component in a simple graph is a maximal subset of mutually connected nodes and the edges between them. Mutually connected means we can find a path from any node in the component to any other node in the component. Every node in the graph belongs to exactly one connected component, with isolated nodes each forming their own component. The graph is called connected if it has only one connected component.

Breadth first search (BFS) and depth first search (DFS) are common algorithms to find connected components (and determine if the graph is connected).

We can find the number of connected components will be equal to the dimension of the nullspace (kernel) of the \(n \times n\) laplacian matrix. The rank \(r\)of this matrix will be equal to the number of its non-zero eigenvalues, and so the number of connected components can be found by \(n-r\). This is the method used to find the number of components in this applet. Note that rounding error in the calculation of eigenvalues may occasionally case an error in this calculation, particularly for large numbers of nodes.

Eulerian Paths and Cycles
An Eulerian cycle traverses every edge of the graph exactly once, beginning and ending with the same node. A graph with a single connected component, or one non-trivial component and isolated nodes, has an Eulerian cycle if and only if every node has even degree. If such a graph instead has exactly two nodes with odd degree, then the graph will have an Eulerian path. This is a walk that traverses every edge exactly once, but begins and ends at different nodes. The path will always begin with one of the nodes of odd degree, and end at the other.
Using the Applet
This is where we explain how to actually use the applet, and some features to look for.
About the Applet
This applet was created using JavaScript and the P5 graphics library.