Problem 5: Graphs

Index

Define a graph to be a near linear space such that every line has exactly two points

GRAPH

1. Any line has precisely two points.

2. Two points are on at most one line.

To obtain a graph from a near-linear space, let's again define a near-linear space S as having a set of points P and a set of lines L. Define the graph G as having a new set of points P' and a new set of lines L'. Again we define P' = L, that is the points of our graph are the lines of the near-linear space S. Let L' = {{p,q}: p and q are distinct intersecting lines of L}. This new space will certainly satisfy the axioms of a graph. Here is an example of a figure of a near linear space and its corresponding graph.

WEB PROJECT:

Please go through the entire web tutorial on graphs at Graph Theory Tutorials.

References: Batten, Beutelspacher & Rosenbaum, Polster.