Create a complete graph with four vertices using the Complete Graph
- 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
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?