Unit 5: Graph Theory-II - Subjective Questions

Eulerian Graph: A connected graph is called an Eulerian graph if it contains a closed walk that traverses every edge exactly once. Such a walk is called an Euler circuit (or Euler line).

Euler Trail (Path): An open walk that traverses every edge exactly once but starts and ends at different vertices.

Necessary and Sufficient Condition (Euler's Theorem):

• A connected graph has an Euler circuit if and only if every vertex has even degree.
• A connected graph has an Euler trail (but not a circuit) if and only if it has exactly two vertices of odd degree. The trail must begin at one odd-degree vertex and end at the other.

Reasoning: Each time an Euler circuit passes through a vertex, it uses one edge to enter and one edge to leave, contributing to the degree. Hence every vertex must have even degree for a closed traversal.

Example: The complete graph has every vertex of degree (even), so it is Eulerian.

Euler's Theorem: A connected graph possesses an Euler circuit if and only if every vertex of has even degree.

Proof of Necessary Condition (Only If):

Assume has an Euler circuit .

• The circuit starts and ends at the same vertex, traversing each edge exactly once.
• Consider any vertex . Every time the circuit enters through one edge, it must leave through another edge.
• Thus, edges incident to are paired up: one for entering, one for leaving.
• Therefore, the number of edges incident to (i.e., ) must be even.

Since was arbitrary, every vertex has even degree.

Sufficient Condition (Sketch): If every vertex has even degree, one can construct an Euler circuit using Fleury's algorithm or by decomposing the graph into edge-disjoint cycles and splicing them together.

Consequence: A graph with any odd-degree vertices cannot have an Euler circuit.

Hamiltonian Cycle: A closed walk (cycle) that passes through every vertex of the graph exactly once (except the starting vertex which is also the ending vertex).

Hamiltonian Path: A path that visits every vertex exactly once (open walk).

Hamiltonian Graph: A graph that contains at least one Hamiltonian cycle.

Difference between Eulerian and Hamiltonian Graphs:

Note: A graph can be Eulerian but not Hamiltonian and vice versa. There is no known simple characterization of Hamiltonian graphs, unlike Eulerian graphs.

These are sufficient conditions (not necessary) for a graph to be Hamiltonian.

Dirac's Theorem (1952): If is a simple graph with vertices such that every vertex has degree , then is Hamiltonian.

Ore's Theorem (1960): If is a simple graph with vertices such that for every pair of non-adjacent vertices and :

then is Hamiltonian.

Relationship: Ore's theorem is more general; Dirac's theorem is a special case of Ore's theorem.

Example: Consider with vertices. Each vertex has degree . By Dirac's theorem, is Hamiltonian. Indeed, is a Hamiltonian cycle.

Important: These conditions are sufficient but not necessary — a cycle graph is Hamiltonian but does not satisfy Dirac's condition for large .

Planar Graph: A graph is called planar if it can be drawn in a plane such that no two edges cross each other (edges intersect only at their common vertices).

Plane Graph: A particular drawing of a planar graph in the plane with no edge crossings is called a plane graph or a map.

Regions (Faces): When a planar graph is drawn in the plane, it divides the plane into connected areas called regions or faces. These include:

• Bounded regions (interior faces): Finite areas enclosed by edges.
• Unbounded region (exterior/infinite face): The single infinite outer region.

Degree of a Region: The number of edges bounding a region. A bridge (cut edge) is counted twice since it borders the same region on both sides.

Key facts:

• The sum of degrees of all regions equals (each edge borders two regions).

Example: is planar and can be drawn with regions (3 bounded + 1 unbounded).

Euler's Formula: For any connected planar graph drawn in the plane:

where = number of vertices, = number of edges, and = number of regions (including the unbounded region).

Proof (by Induction on the number of edges ):

Base Case: If , the graph is a single vertex (), with only one region (). Then:

Inductive Step: Assume the formula holds for all connected planar graphs with fewer than edges. Consider a graph with edges. Two cases arise:

Case 1: is a tree. A tree with vertices has edges and only region. Then:

Case 2: contains a cycle. Remove one edge lying on a cycle. This merges two regions into one, so:

• Edges:
• Regions:
• Vertices: unchanged

The resulting graph is still connected with fewer edges. By induction:

Hence, by induction, the formula holds for all connected planar graphs.

Objective: Prove that for a simple connected planar graph with vertices:

Derivation:

1. In a simple connected planar graph, every region is bounded by at least 3 edges (since there are no loops or multiple edges, the smallest cycle has length 3).

2. Each edge borders at most 2 regions. Summing the degrees of all regions:
   

3. Since each region has degree :
   
   Therefore:
   

4. From Euler's formula , we get . Substituting:
   

5. Multiply through by 3:
   
   

Application: This inequality is used to prove that is non-planar. For : , . Check: . Since , is non-planar.

Claim: (complete graph on 5 vertices) is non-planar.

Given for :

• Number of vertices:
• Number of edges:

Proof using the inequality :

For any simple connected planar graph with :

Substitute :

For to be planar, we would need:

But has edges, and:

This violates the necessary condition for planarity. Therefore, cannot be planar.

Conclusion: is one of the two fundamental non-planar graphs (the other being ) that appear in Kuratowski's theorem.

Claim: (the utility graph) is non-planar.

Given for :

• Vertices:
• Edges:

Proof: For , the standard inequality gives , which does not yield a contradiction. So we use a refined inequality for bipartite planar graphs.

Key observation: is bipartite, so it contains no odd cycles. The shortest cycle (girth) has length 4. Hence every region is bounded by at least 4 edges.

Refined derivation: Since each region has degree :

From Euler's formula, .

But the bound requires:

So we would need . However Euler's formula demands .

This is a contradiction. Therefore is non-planar.

Bipartite planar inequality: For simple bipartite planar graphs, . Here , confirming non-planarity.

Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph that is homeomorphic to either:

• (the complete graph on 5 vertices), or
• (the complete bipartite graph on 3+3 vertices).

These two graphs are called the Kuratowski graphs and are the fundamental obstructions to planarity.

Homeomorphic Graphs: Two graphs and are said to be homeomorphic if both can be obtained from the same graph by a sequence of:

• Series reduction: Removing a degree-2 vertex and merging its two edges into one edge, OR
• Subdivision (edge insertion): Adding a vertex of degree 2 in the middle of an edge.

In other words, homeomorphic graphs differ only by inserting or deleting vertices of degree 2 along edges. Their essential structure (shape) is the same.

Significance: Kuratowski's theorem gives a complete characterization of planar graphs. If a graph contains a subdivision of or , it is non-planar.

Example: The Petersen graph is non-planar because it contains a subgraph homeomorphic to .

Graph Coloring (Vertex Coloring): An assignment of colors to the vertices of a graph such that no two adjacent vertices share the same color. This is called a proper coloring.

k-Colorable: A graph is said to be -colorable if it can be properly colored using at most colors.

Chromatic Number : The minimum number of colors required to properly color the vertices of a graph .

Basic Results:

• if and only if has no edges (null graph).
• if and only if is bipartite (and has at least one edge).
• for the complete graph.
• For any cycle : if is even, and if is odd.

Example: Consider a triangle (three mutually adjacent vertices). Since all three vertices are adjacent to each other, each needs a distinct color. Hence:

Application: Graph coloring is used in scheduling problems, map coloring, register allocation in compilers, and frequency assignment.

Claim: The chromatic number of the complete graph is:

Proof:

Structure of : In a complete graph on vertices, every pair of distinct vertices is adjacent.

Lower Bound ():

• Since every vertex is adjacent to every other vertex, no two vertices can share the same color.
• Therefore, each of the vertices requires a distinct color.
• Hence at least colors are needed: .

Upper Bound ():

• Assign a different color to each of the vertices.
• Since all colors are distinct, no two adjacent vertices share a color.
• This is a valid proper coloring using exactly colors, so .

Combining both bounds:

Examples:

• (triangle)

Bipartite Graph: A graph is bipartite if its vertex set can be partitioned into two disjoint sets and such that every edge connects a vertex in to a vertex in (no edge lies within the same set).

Theorem: A graph is bipartite if and only if it contains no odd-length cycles.

Proof:

() If is bipartite, it has no odd cycle:

• Suppose is bipartite with parts and .
• Any cycle must alternate between and :
• To return to the starting vertex (in the same set), the number of edges must be even.
• Hence all cycles are of even length; no odd cycle exists.

() If has no odd cycle, it is bipartite:

• Assume is connected (else apply to each component). Pick a vertex .
• Partition vertices by distance from : = even distance, = odd distance.
• If any edge joined two vertices of the same set, it would create an odd cycle, a contradiction.
• Hence this is a valid bipartition.

Chromatic Number: For a bipartite graph with at least one edge:

color with color 1 and with color 2.

Regular Graph: A graph in which every vertex has the same degree is called a regular graph. If every vertex has degree , it is called a -regular graph.

Examples:

• Cycle is -regular.
• Complete graph is -regular.
• Petersen graph is -regular (cubic).

Coloring of Complete Bipartite Graph :

The complete bipartite graph has two vertex sets (with vertices) and (with vertices), where every vertex in is joined to every vertex in , but there are no edges within or within .

Chromatic Number of :

Reasoning:

• Assign color 1 to all vertices in .
• Assign color 2 to all vertices in .
• Since edges only go between and , no two adjacent vertices share a color.
• Since has at least one edge, it cannot be colored with just 1 color.

Regularity note: is regular only when , in which case it is -regular.

Four Color Theorem: Every planar graph is 4-colorable. Equivalently, the regions of any map can be colored using at most 4 colors so that no two adjacent regions share the same color.

• First conjectured by Francis Guthrie (1852).
• Proved by Appel and Haken (1976) using a computer-assisted proof — the first major theorem proved with computer aid.

Five Color Theorem: Every planar graph is 5-colorable.

• This is a weaker result but has a relatively short, elegant proof (using Euler's formula and the fact that every planar graph has a vertex of degree ).

Significance:

• Map coloring: Any geographical map (regions as vertices, shared borders as edges) needs at most 4 colors.
• Scheduling & resource allocation: Applications where conflicts form planar structures.
• The Four Color Theorem is a landmark result showing the power of computational methods in mathematics.

Lower bound example: Some planar graphs (like ) actually require exactly 4 colors, so the bound of 4 is tight.

Comparison of Euler Circuit and Hamiltonian Cycle:

Example of Euler Circuit:

Consider a square with both diagonals removed, forming a cycle . Each vertex has degree 2 (even), so an Euler circuit exists: , using all 4 edges once.

Example of Hamiltonian Cycle:

In the same square : visits every vertex exactly once, forming a Hamiltonian cycle.

Graph that is Eulerian but NOT Hamiltonian: Two triangles sharing a single common vertex (bowtie/figure-eight) — all degrees even (Eulerian), but no cycle visits every vertex once.

Graph that is Hamiltonian but NOT Eulerian: The complete graph — it has a Hamiltonian cycle, but every vertex has odd degree 3, so it is not Eulerian.

Degree of a Region: In a plane (planar) graph, the degree of a region , denoted , is the number of edges on the boundary of that region.

Special rule: A bridge (cut edge) that lies on the boundary of only one region is counted twice, because both sides of the bridge face the same region.

Theorem (Handshaking Lemma for Regions): In a connected plane graph with edges:

Proof:

1. Consider any edge of the planar graph.
2. Each edge borders regions in one of two ways:
   • If separates two distinct regions: it contributes to the degree of each of the two regions — total contribution .
   • If is a bridge (borders only one region): it is counted twice for that single region — total contribution .
3. In both cases, each edge contributes exactly to the total sum of region degrees.
4. Since there are edges, the total contribution is:
   

Application: This result is used along with Euler's formula to derive planarity inequalities such as .

Brooks' Theorem: For any connected graph that is neither a complete graph nor an odd cycle, the chromatic number satisfies:

where is the maximum degree of .

Exceptions (where equality holds):

• Complete graphs : .
• Odd cycles : (since ).

General Upper Bound: For any graph:

Relationship with Clique Number :

The clique number is the size of the largest complete subgraph in . Since all vertices in a clique are mutually adjacent, they all need distinct colors:

Combined chain of inequalities:

Example: For : , , , so (complete graph exception).

Significance: Brooks' theorem gives a tighter bound than for most graphs and is fundamental in coloring theory.

Chromatic Polynomial: The chromatic polynomial of a graph is a polynomial that counts the number of ways to properly color the vertices of using at most colors.

Key properties:

• is always a polynomial in .
• The chromatic number is the smallest positive integer for which .
• for all .

Example 1: Complete Graph (triangle):

• First vertex: choices.
• Second vertex (adjacent to first): choices.
• Third vertex (adjacent to both): choices.
  
  At : , and at : . So .

Example 2: Path (three vertices ):

• Vertex : choices.
• Vertex (adjacent to ): choices.
• Vertex (adjacent only to ): choices.
  
  At : , so .

General result for a tree with vertices: .

General result for a path : .

Given:

• Number of vertices:
• Each vertex has degree 3 (so the graph is 3-regular).

Step 1: Find the number of edges .

By the Handshaking Lemma, the sum of all vertex degrees equals twice the number of edges:

Since there are 6 vertices each of degree 3:

Step 2: Find the number of regions using Euler's Formula.

Euler's formula for a connected planar graph:

Substitute and :

Answer:

• Number of edges:
• Number of regions: (including the unbounded region)

Verification (planarity check): . Since , the graph can indeed be planar. (This corresponds to graphs like structure or the prism/triangular prism graph.)