Unit5 - Subjective Questions

Planar Graph:
A graph is called a planar graph if it can be drawn in a plane such that no two edges cross each other except at the vertices. Such a drawing is called a planar representation or embedding of the graph.

Euler's Formula:
For any connected planar graph with vertices, edges, and regions (faces), the relationship is given by:

Explanation of Terms:

• (Vertices): The number of nodes in the graph.
• (Edges): The number of lines connecting the nodes.
• (Regions/Faces): The distinct areas divided by the edges of the graph, including the infinite (unbounded) outer region.

We prove Euler's formula by mathematical induction on the number of edges, .

Base Case:
If , since the graph is connected, there must be only one vertex (). There are no edges to form a closed boundary, so there is only one region (the infinite region), .

Inductive Hypothesis:
Assume the formula holds for any connected planar graph with edges.

Inductive Step:
Let be a connected planar graph with edges.

Case 1: is a tree (contains no cycles).
If is a tree with vertices, then . A tree encloses no finite regions, so .

Case 2: contains a cycle.
Remove an edge that is part of a cycle. The resulting graph is still connected.
In , the number of vertices , edges . Removing a cycle edge merges two regions into one, so .
By the hypothesis, .
Substitute back:

Thus, the formula holds for all connected planar graphs.

Proof:

Let be a connected planar simple graph with vertices, edges, and regions.

1. Degree of a Region: The degree of a region is the number of edges bordering it. In a simple graph (no multiple edges or loops) with , every region must be bounded by at least 3 edges. Therefore, for all regions .
2. Sum of Degrees: The sum of the degrees of all regions is equal to twice the number of edges (since every edge borders exactly two regions, or borders one region twice).
   
3. Inequality:
   Since each region has degree at least 3:
   
4. Substitution into Euler's Formula:
   Euler's formula states: . Therefore, .
   Substitute this into the inequality:
   
   
   
   
   

This inequality is a necessary condition for a simple graph to be planar.

Graph Coloring:
Graph coloring is the assignment of labels (colors) to the vertices of a graph such that no two adjacent vertices share the same color. This is technically known as vertex coloring.

Chromatic Number ():
The chromatic number of a graph is the minimum number of colors required to properly color the graph.

Chromatic Numbers for Specific Graphs:

1. Complete Graph ():
   In a complete graph, every vertex is connected to every other vertex. Therefore, every vertex requires a unique color.
   

2. Bipartite Graph ( or general):
   A bipartite graph's vertex set can be divided into two disjoint sets and such that every edge connects a vertex in to one in . All vertices in can share one color, and all in can share a second color.
   

   
   (Note: If the graph has no edges, , but generally for bipartite graphs with edges, it is 2).

Definition:
A Tree is a connected, undirected graph with no simple cycles. It is a special type of graph that represents a hierarchical structure.

Five Properties of Trees:

1. Path Uniqueness: There is exactly one simple path between any pair of vertices in a tree.
2. Acyclic: A tree contains no loops or cycles.
3. Edge Count: A tree with vertices has exactly edges.
4. Connectivity: Removing any single edge from a tree disconnects the graph (every edge is a bridge/cut-edge).
5. Cycle Creation: Adding any edge between two existing vertices in a tree creates exactly one cycle.

Theorem:
A tree with vertices has exactly edges.

Proof (by Mathematical Induction):

Base Case:
Let . A tree with 1 vertex has 0 edges.
Formula: .
The base case holds.

Inductive Hypothesis:
Assume that any tree with vertices has edges.

Inductive Step:
Consider a tree with vertices.
Since is a tree with a finite number of vertices (), it must contain at least one "leaf" node (a vertex of degree 1). Let be a leaf node and be the edge connecting to the rest of the tree.

Remove vertex and edge from . The remaining graph is still connected and has no cycles, so is a tree.
has vertices. By the inductive hypothesis, has edges.

The original tree has one more edge () and one more vertex () than .
Number of edges in .
Since , then .
Therefore, has edges.

The theorem is proved.

Spanning Tree:
A spanning tree of a connected, undirected graph is a subgraph that is a tree and includes all the vertices of . A graph can have multiple spanning trees. If has vertices, any spanning tree will have vertices and edges.

Minimum Spanning Tree (MST):
Given a connected, weighted graph, an MST is a spanning tree where the sum of the weights of the edges is the minimum possible among all possible spanning trees of that graph. While a graph can have multiple MSTs (if edge weights are not unique), the minimum total weight is unique.

Key Differences:

• Input: Spanning tree applies to any connected graph; MST applies to weighted connected graphs.
• Objective: Spanning tree ensures connectivity without cycles; MST ensures connectivity with minimum cost.

Algorithms to find MST:

1. Kruskal's Algorithm: Adds edges in increasing order of weight, skipping those that form a cycle.
2. Prim's Algorithm: Grows the tree from a starting vertex by always adding the cheapest edge connecting the tree to a non-tree vertex.

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected weighted graph.

Steps:

1. List Edges: List all the edges of the graph along with their weights.
2. Sort: Sort all the edges in non-decreasing order of their weights.
3. Initialize: Create a forest where each vertex is a separate tree.
4. Iterate:
   • Pick the edge with the smallest weight from the sorted list.
   • Check if adding this edge forms a cycle with the edges already included in the MST (i.e., check if the two vertices of the edge belong to the same set/tree).
   • If it forms a cycle, discard the edge.
   • If it does not form a cycle, include it in the MST and merge the two sets of vertices.
5. Termination: Repeat step 4 until the MST contains edges (where is the number of vertices).

Complexity: Generally or , depending on the data structure used for sorting and union-find operations.

Rooted Tree:
A rooted tree is a tree in which one specific vertex is distinguished from the others and is called the root. The edges are often viewed as directed away from the root.

Terminology:

1. Parent: If there is an edge from vertex to vertex , is the parent of .
2. Child: In the above case, is the child of . Every node except the root has exactly one parent.
3. Sibling: Vertices that share the same parent are called siblings.
4. Leaf (External Node): A vertex with no children (degree 1 in undirected context, out-degree 0 in directed context).
5. Height (or Depth) of a Tree: The length of the longest path from the root to any leaf node. (Sometimes defined as the number of edges on the longest path, sometimes number of nodes; usually number of edges).

Comparison of Prim's and Kruskal's Algorithms:

Definition:
A Decision Tree is a specific type of rooted tree used to model decisions and their possible consequences. Each internal node represents a "test" or a "decision" on an attribute, each branch represents the outcome of the test, and each leaf node represents a class label or a final decision.

Structure:

• Root: The starting decision point.
• Branches: Connect nodes, representing the flow based on answers (e.g., Yes/No).
• Leaves: The final output or conclusion.

Example: Sorting 3 numbers (a, b, c)
A decision tree can represent the logic to find the largest number:

1. Root Node: Compare and .
2. If , go Left (Node: Compare and ). If , go Right (Node: Compare and ).
3. From Left (): If , result is . Else result is .
4. From Right (): If , result is . Else result is .

In Discrete Math, decision trees are often used to prove lower bounds on the complexity of sorting algorithms (e.g., comparisons).

Definitions:

• Infix Notation: The operator is placed between operands (e.g., ). This is standard arithmetic notation, often requiring parentheses for precedence.
• Prefix Notation (Polish Notation): The operator is placed before the operands (e.g., ). Parentheses are not required.
• Postfix Notation (Reverse Polish Notation): The operator is placed after the operands (e.g., ). Parentheses are not required.

Conversion of :

1. To Postfix:

   • Convert inner sub-expressions: and
   • Apply the multiplication operator to the results:
   • Result: A B + C D - *

2. To Prefix:

   • Convert inner sub-expressions: and
   • Apply the multiplication operator to the results:
   • Result: * + A B - C D

Tree traversal refers to the process of visiting each node in a tree data structure exactly once. For a binary tree with a Root (), Left Subtree (), and Right Subtree ():

1. Pre-order Traversal (N-L-R):

• Step 1: Visit the Root node ().
• Step 2: Recursively traverse the Left subtree () in Pre-order.
• Step 3: Recursively traverse the Right subtree () in Pre-order.
• Usage: Used to create a prefix expression from an expression tree or to create a copy of the tree.

2. In-order Traversal (L-N-R):

• Step 1: Recursively traverse the Left subtree () in In-order.
• Step 2: Visit the Root node ().
• Step 3: Recursively traverse the Right subtree () in In-order.
• Usage: In Binary Search Trees (BST), this retrieves data in sorted order.

3. Post-order Traversal (L-R-N):

• Step 1: Recursively traverse the Left subtree () in Post-order.
• Step 2: Recursively traverse the Right subtree () in Post-order.
• Step 3: Visit the Root node ().
• Usage: Used to delete the tree (delete children before parent) or evaluate postfix expressions.

Expression:

Steps:
We read the expression from left to right. If the token is an operand, push it to a stack (create a single-node tree). If the token is an operator, pop the top two trees, make them children of the operator, and push the new tree back.

1. Scan 5: Push Node(5).
2. Scan 2: Push Node(2).
3. Scan +: Pop 2, Pop 5. Create tree (5 + 2). Push +.
4. Scan 8: Push Node(8).
5. Scan 3: Push Node(3).
6. Scan -: Pop 3, Pop 8. Create tree (8 - 3). Push -.
7. *Scan :* Pop Tree(-), Pop Tree(+). Create tree where `is root,+is left child,-is right child. Value:(5+2)(8-3). Push`.
8. Scan 4: Push Node(4).
9. Scan /: Pop 4, Pop Tree(). Create tree where / is root, `is left child,4` is right child.

Final Tree Structure:

• Root: /
• Left Child of Root: *
  • *Left Child of :** + (Children: 5, 2)
  • *Right Child of :** - (Children: 8, 3)
• Right Child of Root: 4

Infix Equivalent:

Binary Tree:
A binary tree is a rooted tree in which every internal vertex has at most two children. The children are usually distinguished as the left child and the right child.

Max Nodes Calculation:
Let the root be at height 0 (some definitions start at 1, here we assume height = number of edges from root to deepest leaf, but standard max node formulas often treat level 0 as root).

• Level 0: node.
• Level 1: nodes.
• Level : nodes.

Total maximum nodes for height is the sum of a geometric series:

(Note: If height is defined as the number of nodes on the longest path, say , then Max Nodes ).

The Four Color Theorem:
The Four Color Theorem states that given any separation of a plane into contiguous regions (like a map), no more than four distinct colors are required to color the regions of the map so that no two adjacent regions have the same color.

Relation to Planar Graphs:

1. Dual Graph: Any map can be represented as a planar graph where each region is a vertex, and an edge connects two vertices if the corresponding regions share a boundary.
2. Vertex Coloring: The problem of coloring regions in the map is equivalent to finding the vertex coloring of its planar dual graph.
3. Statement: Thus, the theorem implies that the chromatic number of any planar graph is less than or equal to 4 ( for any planar graph ).

Full Binary Tree (Strict Binary Tree):
A binary tree is full if every node has either 0 or 2 children. No node has exactly one child.

• Property: If a full binary tree has leaves, the total number of nodes is .

Complete Binary Tree:
A binary tree is complete if all levels are completely filled except possibly the last level, and the last level has all keys as left as possible.

• Structure: It looks like a perfect triangle, but the bottom row might stop early (from the right side).
• Significance: Complete binary trees can be efficiently represented using arrays (heap data structure).

Logic:

1. Preorder (Root-Left-Right) gives the Root first. The first element is always the root.
2. Inorder (Left-Root-Right) allows us to identify what is in the Left Subtree vs. the Right Subtree by finding the Root's position.

Construction Step-by-Step:

1. Root: First char of Preorder is A. So, A is the root.
2. Split: Find A in Inorder: D B E (Left) | A | F C (Right).
   • Left Subtree Nodes: {D, B, E}
   • Right Subtree Nodes: {F, C}
3. Left Subtree:
   • Preorder sequence for these nodes: B D E (Next chars after A). Root is B.
   • Inorder split for B (D B E): D (Left) | B | E (Right).
   • So, B has left child D and right child E.
4. Right Subtree:
   • Preorder sequence for remaining nodes: C F. Root is C.
   • Inorder split for C (F C): F (Left) | C | (Empty Right).
   • So, C has left child F and no right child.

Final Tree:

• Root: A
• Left Child: B (which has children D and E)
• Right Child: C (which has left child F)

Kuratowski's Theorem:

Kuratowski's theorem provides a necessary and sufficient condition for a graph to be planar. It states that:

"A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of (the complete graph on 5 vertices) or (the complete bipartite graph on 3+3 vertices)."

Key Concepts:

• : The complete graph with 5 vertices. It is non-planar.
• : The utilities graph (3 houses, 3 utilities). It is non-planar.
• Subdivision: A graph obtained from another by inserting vertices of degree 2 into edges (essentially stretching the edges).

If a graph contains a structure "topologically homeomorphic" to or , it cannot be drawn without crossing edges.

To Prove: Every tree is a bipartite graph.

Definition: 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 one in .

Proof Method:
We can use the property that a graph is bipartite if and only if it contains no odd cycles.

1. Tree Property: By definition, a tree is an acyclic graph. It contains no cycles at all.
2. Cycle Condition: Since a tree has no cycles, it naturally has no odd cycles.
3. Conclusion: Therefore, every tree is a bipartite graph.

Alternative Constructive Proof (Coloring):

1. Pick an arbitrary vertex to be the root.
2. Color with Color 1.
3. Color all children of with Color 2.
4. Color all children of those nodes with Color 1.
5. Generally, color vertices at even levels (distance from root) with Color 1 and odd levels with Color 2.
6. Since there are no edges between vertices at the same level (which would create a cycle), and edges only exist between parent and child (adjacent levels), the coloring is valid with 2 colors ( and ). Thus, it is bipartite.