Graph Planarity. A graph G is planar if it can be drawn in the plane in such a way that no two edges meet each other except at a vertex to which they are incident.
Any such drawing is called a plane drawing of G. For example, the graph K4 is planar, since it can be drawn in the plane without edges crossing. The three plane drawings of K4 are: The five Platonic graphs are all planar. On the other hand, the complete bipartite graph K3,3 is not planar, since every drawing of K3,3 contains at least one crossing. why? To study planar graphs, we restrict ourselves to simple graphs. If a planar graph has multiple edges or loops. Remove loops and multiple edge. Draw without multiple edge.
Insert loops and multiple edges. Euler's Formula If G is a planar graph, then any plane drawing of G divides the plane into regions, called faces. For example, the following graph G has four faces, f4 being the infinite face. It is easy to see from above graph that deg f1=3, deg f2=4, deg f3=9, deg f4=8. n - (m - 1) + (f - 1) = 2 Duality. Euler's Formula. Many theorems in mathematics are important enough that they have been proved repeatedly in surprisingly many different ways.
Examples of this include the existence of infinitely many prime numbers, the evaluation of zeta(2), the fundamental theorem of algebra (polynomials have roots), quadratic reciprocity (a formula for testing whether an arithmetic progression contains a square) and the Pythagorean theorem (which according to Wells has at least 367 proofs). This also sometimes happens for unimportant theorems, such as the fact that in any rectangle dissected into smaller rectangles, if each smaller rectangle has integer width or height, so does the large one. This page lists proofs of the Euler formula: for any convex polyhedron, the number of vertices and faces together is exactly two more than the number of edges. Symbolically V−E+F=2. Graph Theory. Two vertices are called adjacent if they share a common edge, in which case the common edge is said to join the two vertices.
An edge and a vertex on that edge are called incident. See the 6-node graph below right for examples of adjacent and incident: Nodes 4 and 6 are adjacent (as well as many other pairs of nodes) Nodes 1 and 3 are not adjacent (as well as many other pairs of nodes) Edge {2,5} is incident to node 2 and node 5. The neighborhood of a vertex v in a graph G is the set of vertices adjacent to v. The neighborhood is denoted N(v). The degree of a vertex is the total number of vertices adjacent to the vertex.
Each vertex in the undirected graph at right has the following degree: In a directed graph, we define degree exactly the same as above (and note that "adjacent" does not imply any direction or lack of direction). In a directed graph it is important to distinguish between indegree and outdegree. Pay particular attention to nodes 3 and 4 in the above table. Euler's Theorems. References for Graph Theory. Algorithmic Graph Theory. Graph Theory Tutorials. Chris K.
Caldwell (C) 1995 This is the home page for a series of short interactive tutorials introducing the basic concepts of graph theory. There is not a great deal of theory here, we will just teach you enough to wet your appetite for more! Most of the pages of this tutorial require that you pass a quiz before continuing to the next page. So the system can keep track of your progress you will need to register for each of these courses by pressing the [REGISTER] button on the bottom of the first page of each tutorial. Introduction to Graph Theory (6 pages) Starting with three motivating problems, this tutorial introduces the definition of graph along with the related terms: vertex (or node), edge (or arc), loop, degree, adjacent, path, circuit, planar, connected and component.
Euler Circuits and Paths Beginning with the Königsberg bridge problem we introduce the Euler paths. Coloring Problems (6 pages) Adjacency Matrices (Not yet available.)