Graph Theory Notes: Bipartite Graphs, Planar Graphs, Trees & Euler's Formula

Bipartite Graphs

• Definition: A simple graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint sets, say L and R, such that every edge has one endpoint in L and the other in R. Equivalently, G = (A, B, E) with A ∪ B = V, A ∩ B = ∅, and E ⊆ A × B.

• Intuition/metaphor: A bipartite graph represents a division into two groups where edges only go between groups, never inside a group (e.g., men–women marriages, job-application matching where applicants connect to jobs only).

• Fundamental theorem (Characterization): A graph G is bipartite if and only if it has no odd-length cycle. Equivalently, every cycle has even length. So, a graph is bipartite ⇔ All cycles have even length.

  • Notation: For any cycle C in G, |C| is even.

• Classic examples:

  • A marriage graph where men are on one side and women on the other forms a bipartite graph.
  • A tree (which is connected and acyclic) is bipartite.
  • A cycle of even length (C{2k}) is bipartite; a cycle of odd length (C{2k+1}) is not.

• How to check bipartiteness

  • Method 1 (cycle-based): If you can find an odd-length cycle, G is not bipartite. If no odd cycle exists, G is bipartite.
  • Method 2 (bi-partition attempt): Attempt to assign vertices to two parts so that every edge goes between parts. If you encounter a conflict (an edge that must connect vertices within the same part), G is not bipartite; otherwise, you obtain a valid bipartition.

• Degree considerations in bipartite graphs

  • In a bipartite graph with bipartition (L, R), we have the degree-sum relationship: \sum{v \,\in \,L} \deg(v) = \sum{v \,\in \,R} \deg(v) = |E|. this is just the two ends of each edge contributing once to the degree sum on each side.
  • If a bipartite graph is k-regular (all vertices have degree k) with k ≥ 1, then the two parts have the same size: |L| = |R|. Proof: k|L| = \sum{v\in L} \deg(v) = |E| = \sum{v\in R} \deg(v) = k|R| \Rightarrow |L| = |R|. This is a standard result used in many bipartite-graph arguments.

• Complete bipartite graphs

  • Definition: A complete bipartite graph K_{m,n} is a bipartite graph where every vertex in the first part is adjacent to every vertex in the second part. Edge set: E = A × B, where |A| = m and |B| = n.
  • Properties: |V| = m + n, |E| = mn.
  • Star graph as a special case: K_{1,n} is a star graph.

• Maximum edges in a bipartite graph on n vertices

  • The maximum possible number of edges in a bipartite graph with n vertices is attained when the two parts are as balanced as possible.
  • Result: \max |E| = \left\lfloor \dfrac{n^2}{4} \right\rfloor.
  • Achieved by the complete bipartite graph K_{\left\lfloor \dfrac{n}{2} \right\rfloor, \left\lceil \dfrac{n}{2} \right\rceil}.
  • Consequence: If a graph on n vertices has more than \left\lfloor \dfrac{n^2}{4} \right\rfloor edges, it cannot be bipartite.

• Example problems

  • If a bipartite graph G has partitions with |A| = 3 and |B| = 5, the maximum number of edges is |A| \cdot |B| = 3 \cdot 5 = 15.
  • For the plane: K_{2,4} is planar (an example from the course content).

Planar Graphs

• Planar graph definition: A graph is planar if there exists a drawing in the 2D plane with no crossing edges (a planar embedding or planar representation).

• Planar embedding and faces

  • In a planar drawing, the edges and vertices partition the plane into regions called faces (including the unbounded exterior face).
  • The number of faces is denoted by F.
  • The degree of a face, deg(f), is the number of edges along the boundary of that face (counting edges multiple times if they border the face more than once).

• Handshaking lemma for faces

  • In any planar graph drawn in the plane without crossings, the sum of the degrees of all faces is twice the number of edges:
  • \displaystyle \sum_{\text{faces } f} \deg(f) = 2|E|.
  • Since every edge borders two faces, this identity holds.

• Important theorems about planarity

  • Euler's Formula (for connected planar graphs): If a connected planar graph has V vertices, E edges, and F faces, then
  • V - E + F = 2.
  • For planar graphs with C connected components (not necessarily connected):
  • V - E + F = C + 1.
  • Equivalently, V + F = E + C + 1. In particular, for connected planar graphs the form V − E + F = 2 is standard.

• Consequences of Euler’s formula and face-degree bounds

  • If every face has degree at least 3 (a simple planar graph with V ≥ 3), then
  • 2E = \sum \deg(f) \ge 3F \implies F \le \dfrac{2E}{3}.
  • With Euler’s formula for connected graphs (F = E - V + 2), we obtain the classical bound for simple planar graphs:
  • E \le 3V - 6, \quad V \ge 3. (This bound may generalize with caveats when considering multiple components; the standard version is for connected planar simple graphs.)

• Notable nonplanar graphs

  • K5 (the complete graph on 5 vertices) is nonplanar.
  • K3,3 (the utility graph) is nonplanar." The classic visualization is that K5 has too many edges to draw without crossings, and K3,3 cannot be drawn without some edge crossing due to its bipartite nature.

• Planar graphs: basic constructs

  • A plane graph has one face iff it is a forest. This is a useful characterization: a plane embedding with exactly one face implies the graph is acyclic (a forest).
  • Every Tree is a Planar Graph (it can be drawn in the plane with no crossing edges and with exactly one face).
  • Every Forest is a Planar Graph (each connected component is a tree, drawn separately, still no crossings and one exterior face when considered together).

• Planar representations are not unique in appearance, but Euler’s formula ensures the same number of faces across all planar representations of the same planar graph (up to isomorphism).

• Examples from the slides

  • K4 is planar (can be drawn without edge crossings).
  • K5 and K3,3 are classic nonplanar graphs.
  • A couple of sample exercises showed how to count faces in a planar embedding and to note which representations illustrate planarity.

Euler’s Formula and related consequences

• Classic Euler’s formula (for a connected planar graph):
  • V - E + F = 2. where V = number of vertices, E = number of edges, F = number of faces (including the outer face).
• Generalized Euler formula for planar graphs with C connected components:
  • V - E + F = C + 1. Equivalent rearrangements include V + F = E + C + 1.
• Consequences for faces and edges
  • If a connected planar graph has F faces, then using Euler's formula, one can derive values of F given V and E, or deduce upper bounds on E given V.
• Planarity tests via Euler’s constraint
  • The classic way to test planarity is to check for a crossing-free embedding or apply Kuratowski’s theorem (not fully covered in the slides), but Euler’s relation is a foundational check when constructing planar embeddings.

Planar Graphs: Exercises and observations

• Degree of faces and planarity invariants
  • The sum of face degrees equals 2E. If you know the degrees of all faces, you can compute E = (1/2) * sum(deg(f)).
  • The parity of the number of faces with odd degree is always even in any planar graph.
  • If G has only 1 face, G is a forest (as noted earlier).
• Faces counting examples
  • In a planar embedding with F faces, you can count interior faces and the exterior (unbounded) face to get F. The degree of each face is the number of boundary edges.
• Planar graphs and the idea of planarity testing via representations
  • A graph may appear nonplanar in a particular drawing, but if an isomorphic version can be drawn planarly, the graph is planar.
  • Example: K4 is planar because it has a planar embedding without edge crossings, even though some drawings may look crossing-laden.

Hypercubes and Parity (Q_n)

• Hypercube graphs Q_n
  • Vertex set: V = {0,1}^n, i.e., all n-length binary strings.
  • Edge set: E connects two vertices that differ in exactly one bit.
• Parity-based bipartition of Q_n
  • Q_n is bipartite. A natural bipartition is by the parity of the number of 1s in the binary string (or equivalently the parity of the number of 0s, as you choose).
  • Let V1 = {w ∈ {0,1}^n : w has an even number of 1s}, V2 = {w ∈ {0,1}^n : w has an odd number of 1s}.
  • Any edge connects a vertex from V1 to a vertex from V2 because flipping a single bit changes the number of 1s by ±1, changing the parity.
• Consequence: Q_n is bipartite for all n ≥ 1.

Trees and Forests

• Definitions
  • Tree: A connected acyclic undirected graph.
  • Forest: An undirected graph with no cycles (each connected component is a tree).
• Key properties
  • A tree on n vertices has exactly n − 1 edges: |E| = |V| - 1.
  • A forest with n vertices and k connected components has exactly n − k edges: |E| = n - k.
  • A tree is a connected graph with the minimum number of edges to remain connected; equivalently, a connected acyclic graph.
  • A forest is a disjoint union of trees (one or more components), with no cycles.
• Characterizations and equivalent definitions for trees (as given in the notes)
  • Minimally connected: connected, but removing any edge disconnects it.
  • Maximally acyclic: acyclic, but adding any edge creates a cycle.
  • Exactly one of two vertices is connected by a unique path: there is a unique simple path between any two vertices.
  • For a connected planar graph, the number of edges satisfies |E| = |V| − 1 if and only if the graph is a tree (and planarity is automatic since trees are planar).
• Counting edges in trees via path uniqueness
  • In any tree T with n vertices, there is exactly one path between any two vertices; this property underpins several equivalent characterizations of trees.

Planar Graphs: Faces, Planarity, and Euler’s Formula Revisited

• Faces and planarity (summary):
  • A planar embedding partitions the plane into faces; the outer face counts as a face.
  • For a planar graph, the sum of the boundary-edge counts of all faces equals 2E.
  • The number of faces is not affected by different planar representations of the same graph (Euler’s invariant).
• Euler’s formula in other common forms
  • For a connected planar graph with V vertices, E edges, F faces: V - E + F = 2. This can be rearranged as F = E - V + 2.
  • For a general planar graph with C connected components: V - E + F = C + 1. So if you know V, E, and C, you can compute F = E - V + C + 1.
• Consequences and typical questions
  • Counting faces for a given planar embedding is a common exercise.
  • The relation between E and V in planar graphs leads to bounds such as E ≤ 3V − 6 for V ≥ 3 (assuming the graph is simple and connected).
  • A tree, being a planar graph with F = 1, satisfies V − E + 1 = 2 ⇒ E = V − 1, consistent with the tree property.

Planarity Tests and Examples

• Classic nonplanar graphs
  • K5 (complete graph on 5 vertices) is nonplanar.
  • K3,3 (the utility graph) is nonplanar.
• Examples from coursework
  • K4 is planar (one of the standard planar drawings shows a tetrahedron-like embedding in the plane).
  • K2,n is planar for certain small n (e.g., K2,4 is planar as shown in the materials).
• Planar representations and faces (illustrative examples)
  • Counting faces in a planar embedding requires drawing the graph without edge crossings and then counting interior faces plus the exterior face.
  • The degree of a face can vary; the sum of the degrees of all faces equals 2E, and interior faces contribute to the sum along with the exterior face.

Common Results and Quick Theorems (summary from the slides)

• Forests and planarity
  • A plane graph has one face iff it is a forest.
  • Every tree is a planar graph; every forest is a planar graph.
• Maximum edges in bipartite graphs (revisited)
  • For a bipartite graph on n vertices, the maximum possible number of edges is\left\lfloor \dfrac{n^2}{4} \right\rfloor, achieved byK_{\left\lfloor \dfrac{n}{2} \right\rfloor, \left\lceil \dfrac{n}{2} \right\rceil}.
• Planarity bound (connected, simple):
  • If V ≥ 3, then E \le 3V - 6.
  • This bound follows from 2E = sum_f deg(f) ≥ 3F and Euler’s formula V − E + F = 2, yielding E ≤ 3V − 6.
• Euler’s formula for planar graphs (reiterated):
  • For connected planar graphs: V - E + F = 2. For general planar graphs with C components: V - E + F = C + 1.
• Planarity tests and consequences for planarity-related questions
  • A graph is planar iff it has a planar embedding; if a graph is not planar, no embedding without edge crossings exists (K5 and K3,3 are classic obstructions).
• Applications and practice-style questions from the material
  • Determine whether given graphs are bipartite using either odd cycles or bipartitions.
  • For a connected planar graph with given V and E, compute F via Euler’s formula and check face degrees.
  • Use the bipartite bound to assess whether a given graph could be bipartite when given the number of vertices and edges.
  • For hypercubes Qn, recognize bipartiteness via parity arguments; for K{m,n}, compute maximum edges and special cases like stars.

Quick reference formulas (LaTeX)

• Bipartite graphs: no odd cycles; every edge goes between two parts L and R.
• Complete bipartite graphs: K_{m,n} with |V| = m + n and |E| = mn.
• Maximum edges in a bipartite graph on n vertices: \max|E| = \left\lfloor \dfrac{n^2}{4} \right\rfloor, achieved at K_{\left\lfloor \dfrac{n}{2} \right\rfloor, \left\lceil \dfrac{n}{2} \right\rceil}.
• Planar graphs: planar embedding with no edge crossings.
• Face degrees: \sum_{f \in \mathcal{F}} \deg(f) = 2|E|.
• Euler’s formula for connected planar graphs: |V| - |E| + |F| = 2. Generalized with components: |V| - |E| + |F| = C + 1.
• Tree and forest counts: for a tree on n vertices, |E| = n - 1. For a forest with n vertices and k components, |E| = n - k.
• Hypercubes: Q_n is bipartite via parity of number of 1s in the binary string labeling the vertex.
• Maximum edges in planar graphs (connected): |E| \le 3|V| - 6, \quad |V| \ge 3.