Graph Theory- Adv Math

Euler Circuit

is a circuit that uses every edge in the graph exactly once. i.o.w: A Euler circuit is simply an Euler path that starts and ends at the same place

Euler Path

is a trail in a graph that visits every edge exactly once, but does not need to end where it started.

A finite connected graph admits an Euler circuit if and only if every vertex has an even degree

Suppose that G is a finite connected graph with an Euler circuit. Fix such a circuit, and consider any vertex v in the graph. The circuit visits v, and each time it does so, it arrives on one edge and leaves another. Therefore, we can pair off the edge attached to v. Thus, the degree is even, so every vertex has even-degree.

A finite connected graph admits an Euler path if and only if there are at most two vertices with odd degree

Suppose that G is a finite connected graph with an Euler path. Fix such a path, and observe that it can start at a vertex of odd degree and finish at another odd degree vertex. If both endpoints have even degree, every vertex can be visited an even number of times; therefore, an Euler path can exist.

There is no tour of the five-room house that traverses each doorway exactly once

Consider the graph F that abstractly represents the connectivity of the five-room house. So F has six vertices, one for each room of the house and one vertex for the exterior region. The graph F has an edge for each doorway, connecting the vertices associated with each of the rooms that the doorway connects.

The upper two rooms each have degree 5, The lower three rooms have degree 4,5, and 4. The exterior region has degree 9. Since we have 4 vertices with odd-degree, the graph F admits of no Euler path. And so there is no tour of the five-room house that transverses each doorway exactly once.

In every finite simple graph with at least two vertices, there are two vertices with the same degree

Suppose that G is a simple graph with n vertices, where n≥2. Since no vertex has an edge with itself, the degree of any vertex in G is an integer from 0 to n-1, and there precisely n numbers in that range. But notice that if there is a vertex with degree n-1, then it is connected to all the other vertices, and so in this case there cannot be a vertex of degree 0. In other words, the degree 0 and n-1 cannot both arise as the degree of a vertex in G. So there are really only n-1 possibilities for the degree, and so by the pigeon-hole principle, there must be at least two vertices with the same degree.

Simple Graph

Is a graph having no edges from a vertex to itself and also no multiple edges between two of its vertices.

Thus, a simple graph is essentially a set with irreflexive symmetric relation, the edge relation on the vertices.

Planar

it can be represented by vertices and edges in the Cartesian plane without any crossing edges. Such a graph divides the plane into a finite number of faces, the regions bounded by the edges and we count the regions totally outside the graph as one of the faces.

The Euler characteristic of any finite nonempty connected planar nonempty graph is 2

v-e+f = 2

We prove the theorem by induction on the side of the graph (the number of edges appearing in the graph). The statement is true in the graph with one vertex and no edges.

Let us know imagine adding vertices and edges. If we add a since new vertex and a new edge connecting it to a vertex, we had before (in order that the graph is connected) then we have increased v and e by 1, but we have not changed f, so we still have v-e+f =2.

If we add an edge between two vertices we already have, then this new edge cuts on a previous face in two, and so we have increased e and f by 1, but we have not changed v. And so the resulting graph still has v-e-f =2.

Since every finite connected planar graph can be constructed by finitely many steps of these kinds, we see that v-e-f=2 in all of them.

Prove that if a finite graph admits an Euler circuit, then for any particular edge of the graph, there is such an Euler circuit ending with exactly that edge

Prove that in any finite graph, the total degree, meaning the sum of degrees of all the vertices, is always even. Conclude as a corollary that no finite graph can have an odd number of odd-degree vertices

Consider any finite graph with a set of the vertices and a set of edges between them. The total degree is the sum of the degrees, of each vertex. Each edge connects once vertex to another and therefore contributes exactly 2 to the total degree. So the total degree is simply twice the number of edges. Thus, it’s even.

Corollary- No finite graph can have an odd number of odd-degree vertices, then the total degree would be odd, since the sum of any number of even numbers and an odd number or even numbers and an odd number of off numbers is odd. But the proof shows that the total degree in a finite graph is always even, and so this can’t happen.

Let Kn be the complete graph on n vertices. This is the graph with n vertices and an edge between any two distinct vertices. Show for nonzero n that Kn has an Euler circuit if and only if n is odd. For which n does Kn have an Euler path?

Assume that n is a positive integer. A connected finite graph has an Euler circuit if and only if every vertex has an even degree. The graph Kn is a finite connected graph. And since each vertex in Kn is connected to all the others, every vertex has degree n-1, which will be even just in case n is odd. So Kn has an Euler circuit if and only if n is odd.

If n is odd then there is no vertices of odd degree. Therefore, there is an Euler circuit, which is also an Euler path. If n≤ 2, then we will have at most two vertices of odd degree, and so there will n Euler path. If n>3 and even then, we will have n vertices of odd degree, which is too many for there to be an Euler path. So Kn has an Euler path if and only if n is odd or n≤2.

Prove that in any finite graph with exactly two vertices of odd degree, every Euler path must start at one of those odd-degree vertices and end at the other

Suppose that G is a graph with at least one odd-degree vertex, and suppose that we have an Euler path p. By theorem 97 in the main text, this cannot be an Euler circuit, so it must start and end at different vertices. Except for the starting and ending vertices of the path, every time the path enters a vertex via one edge it must depart on another. Therefore, all the intermediate vertices, those arising during the course of the Euler path, must have even degree. And similarly, the starting vertex will have an unmatched outgoing edge, and the ending point will have an unmatched incoming edge, so both of these vertices will have odd degree. In particular, if there are exactly two odd-degree vertices, then every Euler path must start at one of them and end at the other. If a finite graph is connected and has two odd-degree vertices, then there will be an Euler path. The theorem we just proved is helpful when trying to find them, because it tells us where we must start and where we must end.

Let Kn be the complete graph on n vertices. This is the graph with n vertices and an edge

between any two distinct vertices. Show for nonzero n that Kn has an Euler circuit if and only if n is odd. For which n does Kn have an Euler path?

Assume that n is a positive integer. Theorem 97 in the main text shows that a connected finite graph has an Euler circuit if and only if every vertex has even degree. The graph Kn is certainly a finite connected graph. And since each vertex in Kn is connected to all the others, every vertex has degree n − 1, which will be even just in case n is odd. So Kn has an Euler circuit if and only if n is odd.

Suppose that in the city of Konigsberg, the North Prince lives in a castle on the north bank and the South Prince lives in a castle on the south bank. The university is on the east island, but the center of the townspeople’s mathematical discussions is, as we mentioned, at the pub on the center island, with challenges and late-night attempts to “walk the bridges.” Now, the North Prince has a plan to build a new bridge, an eighth bridge, in such a way that from his castle he could traverse all eight bridges and end at the pub, for celebration. Where should he build a bridge that would enable him to do this? Prove that there is essentially only one location for such a bridge, in terms of its connectivity, and furthermore, if such a bridge were built, the South Prince would definitely not have the same ability from his own castle

In the original Königsberg configuration, shown here, all the vertices have odd degree. If the North Prince were to build another bridge from the university (on the east island) to the south bank, parallel to the existing bridge at the lower right, then those two vertices would come to have even degree, making the north bank and the center island the only two vertices of odd degree. Thus, with such a new bridge, there would be an Euler path starting on the north bank and ending at the center island. In other words, the North Prince could walk the bridges from his home to the pub. And indeed, if one were to achieve that feature with one new bridge, it would have to make the east island and the south bank have even degree, and so the new bridge must connect those two vertices. So such a bridge is the only way to do it.

After the North Prince builds his bridge, the infuriated South Prince seeks revenge by building a ninth bridge, which will enable him to traverse all nine bridges exactly once, starting from his own castle and ending at the pub, while simultaneously preventing the analogous ability for the North Prince. Where should he build the ninth bridge?

After the North Prince built the eighth bridge, connecting the university to the south bank, those two locations had even degree in the bridge graph, and the north bank and center island had odd degree. If the South Prince were to build a bridge from the south bank directly to the north bank, then only the south bank and center island would have odd degree. And so the South Prince would be able to walk the bridges on an Euler path from his home in the south to the center island. But there would be no Euler path from the north bank to the center island, because the north bank would have even degree

In order to settle the dispute—and get more customers—the pub keeper decides to build a tenth bridge, which will enable everyone in town to traverse all the bridges, starting at whichever location they wish. Where must the innkeeper build his bridge?

After 9 bridges:

• There are exactly two vertices of odd degree: likely the North Prince's castle and the pub.

• That lets the North Prince start at his castle and end at the pub.

• The South Prince is left out—his castle still has an even degree or is not one of the two odd one the innkeeper wants to build a tenth bridge so that everyone can traverse all 10 bridges, starting at any location they wish. This means we want an Eulerian circuit: a trail that starts and ends at the same point, and uses each bridge exactly once. To make an Eulerian circuit possible all vertices (locations) must have even degree after the tenth bridge is built. So, to make all degrees even, the innkeeper must connect the two odd-degree vertices that is: Build the tenth bridge between the North Bank and the pub.

Across the street from the five-room house considered in this chapter is another five-room house, pictured below, with a slightly different floor plan. Does this house admit a tour traversing each doorway exactly once? Does it admit such a tour starting and ending in the same place?

If we consider the associated graph, with one vertex for each room, including the outside location, which we can think of as one exterior “room,” and with an edge between two vertices for each door that joins the corresponding rooms. If you inspect the graph, you will observe that every room has exactly four doors, except for the entrance foyer (bottom center), which has five doors, and the exterior room, which has nine. In the corresponding graph, therefore, there are exactly two vertices of odd degree, and so by the theorems in the main text, there is an Euler path starting outside and ending in the entrance foyer. Such an Euler path is a tour of the house in such a manner to traverse every doorway exactly once. Every such Euler path must start and end at those odd degree vertices, and so they must all either start outside and end in the entrance foyer or vice versa.

A graph is bipartite if the vertices can be partitioned into two disjoint sets, such that every edge connects a vertex in one set to a vertex in the other set. Prove that if a graph is bipartite, then it has no odd-length cycles. [Hint: An easier case would be to prove that a bipartite graph is triangle-free.]”

Assume we have a bipartite graph, and assume (for contradiction) that it contains an odd-length cycle.

Let’s denote the cycle as:

v1 - v2 - v3. -…- vk - v1 where k is odd (i.e, the cycle has an odd number of edges). Now, in a bipartite graph, we must assign the vertices to two sets (say, U and V) such that adjacent vertices go into opposite sets. Lets say: v1 ∈ U → then v2 ∈ V, c3 ∈ U, u4 ∈ V. Because we're alternating sets at each step, then: if K is odd, vk will land in the opposite set from v1. But vk is connected back to v1 by the last edge in the cycle. That means they must be in different sets. This contradiction shows that an odd-length cycle cannot exist in a bipartite graph

Prove that every n-gonal prism, the solid with a regular n-gon on two ends and edges connecting the corresponding vertices, has v − e + f = 2

v: number of vertices

e: number of edges

f: number of faces

Imagine a 3D shape made by stacking two regular n-gons (one on top, one on bottom) and connecting corresponding vertices with vertical edges. This creates:

• 2 bases (top and bottom): both n-gons

• n side faces, each a rectangle (or square, if height matches base)

Vertices (v)

• Each base has n vertices

• Top and bottom are disjoint → total vertices:

v=n+n = 2n

Edges (e)

Edges come from:

Each base: n edges on top + n on bottom → 2n

1. Vertical edges connecting top and bottom: 1 per vertex → n

Total edges:

e = 2n+n = 3n

Faces (f)

• 2 polygonal bases

• n rectangular side faces

Total faces:

f=n+2

v−e+f → 2n−3n+(n+2) → (2n−3n+n)+2 → 0+2 → 2

Thus, every n-gonal prism satisfies: v−e+f=2

Construct a triangulation of the torus, and compute the Euler characteristic of it.

Consider the following square region, cut into two triangles by the diagonal. Imagine that you have cut out the square shape and that the material is very flexible and stretchy. We shall form it into a torus.

Roll the square from bottom to top, so as to bring the bottom edge into coincidence with the top edge, in effect identifying the two horizontal sides. This will make a small horizontal tube, with circular ends, corresponding to the double-marked edges of the square at the left and right. We may now bend this tube around so as to join the two circular boundaries, thereby making the familiar torus or doughnut shape. Ultimately, we have formed a torus from the square by identifying both the upper and lower edges and the left and right edges, respectively, with the indicated orientations. In particular, all four corners of the square have become identified with a single point on the torus. And so we have made a triangulation of the torus with just one vertex; we have three edges: the original diagonal edge, the top edge (same as the bottom edge), and the left edge (same as the right edge); and we have two faces, the two triangular regions visible in the square. Thus, v = 1, e = 3, and f = 2, which results in 1-3+2 = 0.