## Graph Creator

**Vertex Tools**and

**Edge Tools**to create your graph, and then use the

**Graph Explorer**to investigate your graph and the problem it represents. At any point the

**Clear All**button on the bottom right can clear your entire workspace.

**Vertex Tools:**

**Add
Vertex** creates a new vertex on your workspace. Vertices are automatically
labeled sequentially A–Z then A'–Z'. The maximum number of vertices allowed on
the workspace is 52.

**Select
Vertex** selects one or several vertices to move them or change their
properties. To select more than one vertex, either shift+click individual
vertices or use your mouse to draw a rectangle around the vertices you would
like to select.

**Snap to
Grid** displays a grid that all vertices will snap to when moved or added.
This is helpful when arranging a graph into a rectangular array.

**Label** changes the letter label of a vertex. It can only be used on one
vertex at a time. Labels are restricted to the letters A–Z and A'–Z' and must be
unique.

**Show Degree** toggles between showing and hiding the degree of each
vertex.

**Edge Tools:**

**Add Edge**
adds an edge between two vertices. Click once on each endpoint to draw the edge.
If you click the same vertex twice, it creates a loop. Several edges can be
added between the same pair of vertices.

**Add
Directed Edge** adds directed edges between two vertices. The direction is
determined by the order in which the vertices are clicked.

**Bend
Edge** bends or stretches any existing edge. When the tool is activated, all
edges will display a red control point. Move the control point to bend the edge.

**Select
Edge** selects one or several edges to change their properties. This tool
cannot move edges. Several edges can be selected at once in the same manner as
with the Select Vertex tool.

**Complete Graph** draws a complete graph using the vertices in the
workspace. It erases all existing edges and edge properties, arranges the
vertices in a circle, and then draws one edge between every pair of vertices.

**Weight** sets the weight of an edge or set of edges. The default weight
of all edges is 0. Weights can be any integer between –9,999 and 9,999.

**Show Weight** toggles between showing and hiding the weights. Hiding the
weight does not erase the value.

**Directed** toggles between showing an edge as a directed or undirected
edge.

**Direction** switches the direction of a directed edge.

**Graph Explorer:**

**Highlighter** highlights vertices and edges. Several elements can be
highlighted at once in the same manner as with the Select Vertex tool. Click the
blank background to deselect everything. If edges are highlighted, a running Sum
of All Weights will be displayed in the toolbar.

**Highlight Euler Path** highlights edges on your graph to help you find
an Euler path. Edges that would not create an Euler path are restricted.

**Highlight Hamiltonian Path** highlights edges on your graph to help you
find a Hamiltonian path. Edges that would not create a Hamiltonian path are
restricted. A running Sum of All Weights will be displayed in the toolbar as you
build your path.

**Common Tools:**

**Delete
Selected** deletes individual vertices or edges using the tools on the
respective toolbars.

**Color
Palette** changes the color of selected vertices or edges. If an element color
is changed, that will become the default color for new elements of that type.

**Hide
Toolbar** is in the bottom center of the toolbar. Use it to hide the toolbar
and give yourself more workspace to create and explore your graph.

Create a complete graph with four vertices using the **Complete Graph**
tool.

- Can you move some of the vertices or bend some of the edges so that the edges intersect only at the vertices? That is, can the graph be drawn so that none of the edges intersect one another?
- A graph is said to be
*planar*if it can be drawn on a plane so that the edges intersect only at the vertices. Is this graph planar?

Create a complete graph with five vertices.

- Is this graph planar?
- What is the fewest number of edges you would need to remove so that the resulting graph would be planar?

A *path* is a series of vertices where each consecutive pair of vertices
is connected by an edge. In other words, if you can move your pencil from vertex
A to vertex D along the edges of your graph, then there is a path between those
vertices. A *connected graph* is a graph where all vertices are connected
by paths. Create a connected graph, and use the Graph Explorer toolbar to
investigate its properties.

Find an Euler path:

- An Euler path is a path where every edge is used exactly once. Does your graph have an Euler path? Use the Euler tool to help you figure out the answer.
- A
*circuit*is a path that starts and ends at the same vertex. Does your graph have an Euler circuit? - If there is no Euler path or circuit, how can you change your graph so that it will?

Find a Hamiltonian path:

- A Hamiltonian path is a path where every vertex is used exactly once. Does your graph have a Hamiltonian path? Use the Hamiltonian tool to help you figure out the answer.
- Does your graph have a Hamiltonian circuit?
- Try adding weights to the edges of your graph. Can you find the Hamiltonian circuit for your graph that has the least total weight of the edges?