Details

Introduction

A graph is a network of vertices and edges (curved or straight line segments) connecting these vertices.

A practical example is a map of a set of towns connected by roads. Roads cannot join outside of towns though they may cross (think overpass).

In a planar graph the lines (roads) do not cross.

The degree of a vertex is the number of edges connecting on it.

"Vertex-alternating" means that the degrees of any two neighboring vertices differ.

The degree of a face is the number of edges (or vertices) surrounding it.

"Face-alternating" means that the degree of any two adjacent faces is not the same.

The outside area also counts as a face.

The system does not check whether a graph is alternating. You must do the verification visually.

Dual graphs

Each planar graph has a dual. To obtain the associated dual graph of a given graph you reverse the roles of towns and areas (vertices and faces).

The Demonstration controls are described in the following discussion.

"challenge" control

Each challenge displays a solution to a mathematical problem (see the following list for details).

You are invited to find other solution graphs, ones using fewer vertices, or ones with a new combination of numbers of vertices and faces.

The "Free Play" challenge shows a part of an alternating planar graph. Try to complete it!

Here are the challenges:

• Hamilton's puzzle • Hamilton paths and Hamilton circuits (on Platonic solids)

• connect eight vertices of degree seven with each other, using the fewest board positions • connect nine vertices of degree eight with each other, using the fewest board positions

• find a vertex-alternating graph with six vertices • find a vertex-alternating graph with seven vertices • find a vertex-alternating planar graph with eight vertices • find a vertex-alternating planar graph with nine vertices • find a vertex-alternating planar graph with 10 vertices • find a vertex-alternating planar graph with 11 vertices • find a vertex-alternating planar graph with 12 vertices

Can you find solutions to some of them without looking at the solution?

"<<", "<", ">", ">>" setter bar

This lets you jump to the first, previous, next, or last challenge.

"grid 1"

This button displays a grid with unit spacing.

"grid 2"

This button displays a grid with 5-unit spacing. This grid is very useful when you start designing your graph, but can be annoying later; therefore you can switch it off separately.

"bg"

This button displays a light gray background that is easier on the eyes than a white background.

"opacity"

This slider controls the opacity of the background grid.

action "click"

This lets you click a board position to show its coordinates, even when the position is not empty.

The coordinates (in grid units) are displayed on the left border.

action "vertex"

Click a board position to drop a square representing a vertex of the graph.

You can select a numbered vertex using the "vertex" drop-down menu.

Vertices can carry numbers that represent their degree.

Vertices must be placed at least two units apart.

action "mark face"

Click a board position that is not occupied by a vertex or line segment.

A number (selected using the "face" drop-down menu) is dropped on the board representing the numbers of vertices surrounding the area you clicked.

The system does not automatically check this number for correctness.

(However, see action "count v" that counts vertices for a clicked area.)

action "line"

Click the starting position to make a red square appear. Pink points mark where you can click next. You can always go into one of the eight main directions. Now click the target position to finish the line, which ends in a green square.

action "polyline"

Click a starting position to start a polyline. A red square appears. Pink points mark where you can click next. You can always go into one of the eight main directions, but you cannot go back. Click several positions that define the desired polyline. When you are done, click the last clicked position again to finish the polyline.

You cannot turn back in the next move.

Do not place vertices next to each other.

action "v chain"

This action is similar to the action "polyline", with the difference that every click creates a vertex that is connected by a straight line to the previously created vertex, resulting in a "vertex chain".

action "v degrees"

This causes the system to calculate the degrees of all vertices. In other words, for each vertex the number of lines connecting to this position is calculated and displayed in a colored square (if it is greater than zero).

Different degrees use different colors.

This is most useful when you want to check whether your graph is a vertex-alternating graph.

action "count v"

Whereas the degree of all vertices of a given graph can be calculated at once by clicking the action "v degrees", for the degrees of the faces you must click each area separately to let the system do the calculation.

Click an empty board position or a position that has an area marker already. The system calculates the number of surrounding vertices for the clicked area and displays it at the clicked position.

For "count v" to work, at least two lines must meet at each vertex. Furthermore, no area may contain another area.

The resulting count is shown at the clicked position.

If you click anywhere in the outside area of your graph, this action will still provide the correct result.

If you have two disconnected graphs, you still can use "count v"; just make sure that you click the board immediately below the partial graph you want to apply it to.

To avoid program loops, do not use the action "count v" in graphs that contain crossings. The system recognizes most crossings and prohibits the use of this action. (However, the system does not detect the case of one diagonal crossing another diagonal line segment.)

action "delete"

Click a position to erase its content.

action "delete line"

Click a position to erase its content. If you clicked a position with a straight line, then the whole extent of the line or polyline containing this straight part will be erased.

action "delete faces"

This deletes all face markings (this is useful during editing).

action "delete horizontal"

Click the board. All entries on the same row as the clicked position are deleted.

action "delete vertical"

Click the board. All entries on the same column as the clicked position are deleted.

action "copy"

Click the board. The part of the graph to be copied is highlighted. It is the rectangular area whose lower-left corner is the clicked position. The size of the rectangle is determined by the "copy size" controls. You can repeatedly click the board and change the copy size. Once you are satisfied with your choice, select the action "paste".

action "paste"

Click the board at the position where you want to place the stored part of your graph (see action "copy"). You can click the board at various placed to create more copies

action "reset"

This re-creates the default setup.

action "clear"

This clears the board.

"vertex" drop-down menu

Select the degree of the vertex that you want to paint on the board.

Then select the action "vertex" and click the board to paint this vertex onto the board.

"face mark" drop-down menu

Select the degree of the vertex that you want to paint on the board.

Then select the action "mark face" and click the board to paint this vertex onto the board.

"copy size" controls

Here you select the horizontal and vertical extent of a rectangular region of your graph that is to be copied to.

These and values will only be recognized by the system when the action "copy" is active and you have clicked the board.

"shift" controls

Click "N" to shift the whole graph one unit up; similarly click "E", "S", or "W" to move the whole graph one unit right, down, or left, respectively.

"flip"

Click "" to flip the graph horizontally or "" to flip the graph vertically.

(You can also flip parts of a graph: you first copy and paste part of your graph to a different challenge, flip the part, then copy and paste the flipped part to your original graph.)

"undo"

Click "undo" to undo your last editing step.

It is not recommended to use "undo" during the creation of a polyline or a vertex chain.

If you undo a step during the creation of either a polyline or a vertex chain, then the position of the previous move is turned into a green vertex.

"store"/"restore"

Click "store" to save the graph; click "restore" to restore it.

It is not recommended to use "store" during the creation of either a polyline or a vertex chain.

If you store a graph during polyline creation or vertex chain creation, then the position of the previous move is turned into a green vertex when you restore the graph.

last click was at

This shows the coordinates (in grid units) of the last clicked board position.

vertices

This counter shows how many vertices are in the graph.

(vertices) statistics

This lists how many vertices are of degree 1, 2, 3, 4, 5, 6, 7, and 8, which gives a sort of fingerprint of a planar graph.

The statistics of the degrees of vertices and faces helps you to decide whether two graphs are the same or duals of each other.

Note that (green) vertices that do not display a number are only counted in the total, but not in the statistics.

marked faces

This counter shows how many faces have been given degree markers.

Remember that for alternating planar graphs one usually demands that all vertices are of degree 3 or higher.

(marked faces) statistics

This lists how many faces are of degree 1, 2, 3, 4, 5, 6, 7, and 8, which gives a sort of fingerprint of a planar graph.

The statistics of the degrees of vertices and faces help you to decide whether two graphs are the same or duals of each other.

Notes

This Demonstration allows crossings; hence the graph editor is somewhat more versatile than the graph editor of the Demonstration "Alternating Planar Graphs". Also, there is an additional display of the number of used board positions in this Demonstration.

To avoid program loops, do not use the action "count v" in graphs that contain crossings. The system recognizes most crossings and prohibits the use of this action. (However, the system does not detect the case of one diagonal crossing another diagonal line segment.)

Only up to eight lines can connect to a vertex in this Demonstration.

The action "count v" only works correctly if all vertices are of degree 3 or higher, that is, if at least three lines meet at each vertex.

Do not place vertices next to each other, because it will not be clear whether they are meant to be joined or not.

The system does not calculate whether your graph is indeed a vertex-alternating or face-alternating graph.

History

The problems presented here were first published as the Zillions game "Graph Puzzles" by the same author.

A very similar subject relating to planar graphs is covered by the Zillions game "Roadmaps", also by the same author.