## Graph Creator

Grade:

6-8, 9-12

Standards:

Math Content:

Geometry

Use this vertex-edge tool to create graphs and
explore them. Investigate ideas such as planar graphs, complete graphs,
minimum-cost spanning trees, and Euler and Hamiltonian paths.

Use the

**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?