Edge and Vertex Connectivity
He used graphs to solve the famous Königsberg bridge problem. Program Structure: A compiler builds a graph to represent relationships between A graph that have nonempty set of vertices connected at most by one edge is called simple. In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between A vertex may exist in a graph and not belong to an edge. V and E are usually taken to be finite, and Many practical problems can be represented by graphs. Emphasizing their application to. A polyhedron is a solid object whose surface is made up of a number of flat faces which themselves are bordered by straight lines. Each face is.
Furthermore, since a polyhedron can not have fewer than three edges at any vertex or any faces with fewer than 3 sides, these are obvious necessary conditions that a graph must obey in order for it to be the edge-vertex graph of some convex 3-dimensional polyhedron. However, these conditions are not sufficient for a graph to arise from a convex polyhedron. Clearly, a graph corresponding to a polyhedron can not have a single edge whose removal disconnects the graph into more than one piece, as would be true for the graph below: The graph below is 3-valent and has faces which are at least three-sided.
Can you convince yourself that it does not correspond to any convex 3-dimensional polyhedron, but that there is a non-convex 3-dimensional polyhedron which does have this as its edge-vertex graph? The polyhedron, when you find it, has four triangular faces and two hexagonal faces! In a rather curious situation, the solution to this problem, finding conditions on a graph that it be isomorphic to have the same structure as the vertex-edge graph of a convex 3-dimensional polyhedron, was completely answered in the early part of the 20th century.
This work was done by the great German geometer and algebraist Ernst Steinitz Steinitz's work was published in German and, unfortunately, did not become widely known for quite some time. The catalyst for the reformulation of what Steinitz had done was the "translation" of his work into modern graph theory terminology.
A graph G is isomorphic to the vertex-edge graph of a 3-dimensional polyhedron i. G is 3-polytopal if and only if G is planar and 3-connected.
The property of being 3-connected requires that for any pair of vertices u and v of the graph, there are at least three paths between u and v whose only vertices in common are u and v. The diagram below offers a "schematic" view of what such paths might look like for two typical vertices in a graph. The diagram omits other edges that might be present at the dots shown. Amazingly, Steinitz's Theorem enables one to study the combinatorial theory of 3-dimensional convex polyhedra by drawing diagrams in 2 dimensions!
These appeared in areas involving Hamiltonian circuits a tour of the vertices, starting and ending at the same vertex, visiting each vertex once and only oncecoloring problems, and matchings disjoint sets of edges. Perhaps the greatest progress concerned existence theorems for 3-dimensional convex polyhedra.
Such questions now were reduced to constructions of planar graphs. The study of Hamiltonian circuits was spurred by the graph theory version of Steinitz's Theorem. Thus, David Barnette and others found a vertex, 3-valent, 3-polytopal non-Hamiltonian graph, and was led by his work to the still open conjecture that planar 3-valent 3-connected bipartite graphs have a Hamiltonian circuit. Another milestone in the theory of Hamiltonian circuits was Grinberg's amazing result, described below.
Euler's Polyhedral Formula: Part II
Let G be a plane graph with Hamiltonian circuit H, let pk' denote the number of k-gonal faces of G which are interior to the circuit H, and let pk'' denote the number of k-gonal faces of G which are exterior to the circuit H. Figure 2 For the diagram above and the Hamiltonian circuit shown in blue we have four interior faces labeled in red which are a 3- 4- 6- and 7-gon.
The faces which are exterior to the blue Hamiltonian circuit labeled in green are a 3-gon, two 4-gons, a 5-gon, and a 6-gon. Grinberg's Theorem states that the following relationship must hold between the faces lying in the interior and exterior of such a Hamiltonian circuit: You should verify that the numbers associated with the Hamiltonian circuit in Figure 2 satisfy the equation above.
As an example of the power of Grinberg's Theorem, one can use it to show that the 3-valent polyhedron whose graph is shown below has no Hamiltonian circuit. The lack of a Hamiltonian circuit follows from the fact that all of the faces in the graph except one have a number of sides which leaves a remainder of 2 when divided by 3. Put differently, all the faces have a number of sides congruent to two mod 3, except for one face, the 9-gon.
Although Tutte's vertex graph contains sets of 3 edges which will disconnect the graph into two pieces, each of which contains a circuit, for the graph below, one has to cut 5 edges to disconnect the graph into two pieces, each of which contains a circuit. Eberhard Type Theorems Look again at the equation that a 3-valent plane graph must satisfy: Given a solution of this equation in non-negative integers, does there exist a convex 3-dimensional polyhedron P such that the number of sides of the faces of P are the given ones?
However, because there is no restriction on the value of p6 for a plane graph, the following question arises.
It was this problem that a blind 19th century geometer, Victor Eberhard, raised and thought he had solved in his book Zur Morphologie der Polyeder. Although Eberhard's "Theorem" was given by Eberhard, his proof does not meet modern standards of rigor. However, the proof and some extensions and generalizations of the original proof and theorem are somewhat technical. The Euler relation for plane 4-valent graphs is: Then I will show a slightly simpler proof with easier-to-realize drawings.
Rather than show a general proof, I will show an example which indicates how to proceed in the general case. First, note that what the 4-valent Euler relation tells us is that every 4-valent 3-polytopal graph i. The block is constructed by placing k-4 dots along the left hand side and bottom of a square note: The dots are joined in the order of top dot on the left to the left dot on the bottom.
Next, one joins the next dot down on the left to the next dot to the right on the bottom, etc. Note that this results in a group of k-4 triangles hugging a k-sided region in the square.
The internal vertices in the block are 4-valent, and the other faces within the block are all 4-gons, which can be used as generously as we want.
AMS :: Feature Column from the AMS
One now takes the individual blocks, one for each k-gon, and lays them out along the anti-diagonal of an array. For blocks with a 5-gon and 6-gon we get the diagram shown below: Note that in doing so only 4-gon regions are added, but we are allowed as many of these as we would like.
Notice also that all the interior vertices above are 4-valent and that the number of vertices along the left and bottom are equal. InClaude Berge formulated another conjecture about graph coloring, the strong perfect graph conjecture, originally motivated by an information-theoretic concept called the zero-error capacity of a graph introduced by Shannon.
- Secondary menu
- 3-D figures formed by polygons enclosing regions in space.
- Euler's Formula
The conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by ChudnovskyRobertsonSeymourand Thomas in Graph coloring has been studied as an algorithmic problem since the early s: One of the major applications of graph coloring, register allocation in compilers, was introduced in Since a vertex with a loop i.
The terminology of using colors for vertex labels goes back to map coloring. A coloring using at most k colors is called a proper k-coloring. A graph that can be assigned a proper k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k.
A subset of vertices assigned to the same color is called a color class, every such class forms an independent set. Thus, a k-coloring is the same as a partition of the vertex set into k independent sets, and the terms k-partite and k-colorable have the same meaning.
Chromatic polynomial[ edit ] All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E3 red admits a 1-coloring, the others admit no such colorings. The green graph admits 12 colorings with 3 colors.