Ch. 9: Planarity

From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 9.1. Planar Graphs 9.2. Embedding Graphs on Surfaces 9.3. Excursion: Graph Minors 9.4. Exploration: Embedding Graphs in Graphs

82 flashcards · Mathematics · by lakesare

Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses

A theme park has six attractions A1, …, A6. Walkway tubes are to join every pair of attractions except A1–A4, A2–A5 and A3–A6. Can all the tubes be built so that no two of them cross?
Yes. The graph ( K6K_6K6 minus three disjoint edges) can be redrawn with no crossing edges: (a) drawn with crossings, (b) the same graph drawn without.
When is a graph planar, and when is it a plane graph?
Planar: it can be drawn in the plane with no two edges crossing. Plane graph: it is drawn that way. A graph that is not planar is nonplanar. The same planar graph HHH : (a) not drawn as a plane graph, (b) drawn as a plane graph.
What is the Three Houses and Three Utilities Problem, and which graph question is it?
Can three houses each be connected to gas, water and electricity with no lines crossing? In graph terms: is K3,3K_{3,3}K3,3 planar? Reportedly introduced by the American puzzle-maker Sam Loyd, Sr. in 1900.
Name four classes of graphs that are always planar.
Cycles, paths, stars and trees.
A plane graph divides the plane into connected pieces called regions; the one unbounded piece is the exterior region.
In a plane graph, what is the boundary of a region RRR ?
The subgraph whose vertices and edges are incident with RRR . A plane graph with six regions R1,…,R6R_1, \dots, R_6R1,…,R6 (exterior: R6R_6R6 ) and the boundary of each.
In a plane graph, how many regions have a given edge eee on their boundary?
One if eee is a bridge, two otherwise. The one region of a bridge need not be the exterior region. The bridge uvuvuv is on R6R_6R6 only; vyvyvy is on R2R_2R2 and R3R_3R3 .
In a plane graph, how does the number of regions change when you delete an edge that is (a) not a bridge, (b) a bridge?
(a) One region fewer: the two regions on its sides merge. (b) No change. In (b) the graph becomes disconnected.
GGG is a connected plane graph with at least three edges. At least how many edges does the boundary of each region have?
3
The Euler Identity (Theorem 9.1) If GGG is a connected plane graph of order nnn and size mmm with rrr regions, then … ?
n−m+r=2\boldsymbol{n - m + r = 2}n−m+r=2 n=9n = 9n=9 , m=13m = 13m=13 , r=6r = 6r=6 : 9−13+6=29 - 13 + 6 = 29−13+6=2 .
Who first observed the Euler Identity n−m+r=2n - m + r = 2n−m+r=2 , and how was it first reported?
Leonhard Euler, in a letter to Christian Goldbach dated November 14, 1750. It first appeared in print in 1752.
The Euler Identity: a connected plane graph of order nnn and size mmm with rrr regions has n−m+r=2n - m + r = 2n−m+r=2 .How does the proof go?
Take a counterexample GGG of smallest size and delete an edge that is not a bridge: this lowers mmm and rrr by 1 each. Trees satisfy the identity directly ( m=n−1m = n - 1m=n−1 , r=1r = 1r=1 ), so GGG is not a tree and has a non-bridge eee . G−eG - eG−e is smaller, so n−(m−1)+(r−1)=2n - (m - 1) + (r - 1) = 2n−(m−1)+(r−1)=2 , i.e. n−m+r=2n - m + r = 2n−m+r=2 . Contradiction.
A connected planar graph has order 7 and size 9. How many regions does a drawing of it as a plane graph have, and does it depend on the drawing?
4, in every drawing. By the Euler Identity, r=2−n+m=2−7+9r = 2 - n + m = 2 - 7 + 9r=2−n+m=2−7+9 .
Theorem 9.2 If GGG is a planar graph of order n≥3n \ge 3n≥3 and size mmm , then … ?
m≤3n−6\boldsymbol{m \le 3n - 6}m≤3n−6 Planar graphs cannot have too many edges.
If GGG is a planar graph of order n≥3n \ge 3n≥3 and size mmm , then m≤3n−6m \le 3n - 6m≤3n−6 .What is the key step of the proof, for connected GGG ?
Count the edges on the region boundaries: 3r≤∑mi≤2m3r \le \sum m_i \le 2m3r≤∑mi≤2m . Each of the rrr regions has mi≥3m_i \ge 3mi≥3 boundary edges, and each edge is counted at most twice (once if it is a bridge). The Euler Identity then gives 6=3n−3m+3r≤3n−3m+2m=3n−m6 = 3n - 3m + 3r \le 3n - 3m + 2m = 3n - m6=3n−3m+3r≤3n−3m+2m=3n−m .Disconnected GGG : add edges to get a connected plane graph, which has even more edges.
Why does the bound m≤3n−6m \le 3n - 6m≤3n−6 for planar graphs (order nnn , size mmm ) need n≥3n \ge 3n≥3 ?
K2K_2K2 is planar, but 1>3⋅2−6=01 > 3 \cdot 2 - 6 = 01>3⋅2−6=0 .
What quick test on the order n≥3n \ge 3n≥3 and size mmm shows that a graph is nonplanar?
m>3n−6\boldsymbol{m > 3n - 6}m>3n−6 This is the contrapositive of m≤3n−6m \le 3n - 6m≤3n−6 for planar graphs. It only proves nonplanarity; m≤3n−6m \le 3n - 6m≤3n−6 proves nothing.
Corollary 9.3 Every planar graph contains a vertex of degree … ?
5 or less. If every degree were at least 6, then 2m=∑deg⁡v≥6n2m = \sum \deg v \ge 6n2m=∑degv≥6n , so m≥3n>3n−6m \ge 3n > 3n - 6m≥3n>3n−6 .
Why is K5K_5K5 nonplanar?
Its size m=10m = 10m=10 exceeds 3n−6=93n - 6 = 93n−6=9 . A planar graph of order n≥3n \ge 3n≥3 has at most 3n−63n - 63n−6 edges.
A connected plane graph of order n≥3n \ge 3n≥3 has exactly 3n−63n - 63n−6 edges. What are its regions like?
Every region's boundary is a triangle, the exterior region's included. Equality in 3r≤∑mi≤2m3r \le \sum m_i \le 2m3r≤∑mi≤2m forces every mi=3m_i = 3mi=3 and no bridges.
When is a graph maximal planar?
It is planar, but adding an edge between any two nonadjacent vertices makes it nonplanar. Equivalently: planar, and not a proper spanning subgraph of another planar graph. Maximal planar: K3K_3K3 , K4K_4K4 and K5−eK_5 - eK5−e .
A maximal planar graph GGG has order n≥3n \ge 3n≥3 and size mmm . What is mmm , and what does every region of a plane drawing of GGG look like?
m=3n−6\boldsymbol{m = 3n - 6}m=3n−6 , and every region is bounded by a triangle. For n≤4n \le 4n≤4 the only maximal planar graph of order nnn is KnK_nKn .
Why does the bound m≤3n−6m \le 3n - 6m≤3n−6 for planar graphs (order nnn , size mmm ) fail to show that K3,3K_{3,3}K3,3 is nonplanar?
K3,3K_{3,3}K3,3 satisfies it: m=9≤12=3n−6m = 9 \le 12 = 3n - 6m=9≤12=3n−6 .
How do you prove that K3,3K_{3,3}K3,3 is nonplanar?
A plane drawing would have r=5r = 5r=5 regions, each with at least 4 boundary edges, forcing m≥10m \ge 10m≥10 ; but m=9m = 9m=9 . r=5r = 5r=5 from the Euler Identity 6−9+r=26 - 9 + r = 26−9+r=2 . At least 4 edges because K3,3K_{3,3}K3,3 has no triangles; no bridges, so 2m=∑mi≥202m = \sum m_i \ge 202m=∑mi≥20 .So the Three Houses and Three Utilities Problem has no solution.
Where was Kazimierz Kuratowski when he discovered his planarity theorem?
In Lvov, as a professor at the Technical University of Lvov (from 1927). The mathematicians there often worked in tea shops and cafés. He moved to the University of Warsaw in 1934.
Must a graph of order n≥3n \ge 3n≥3 and size m>3n−6m > 3n - 6m>3n−6 contain K5K_5K5 or K3,3K_{3,3}K3,3 as a subgraph?
No. n=7n = 7n=7 , m=16>15m = 16 > 15m=16>15 , so this graph is nonplanar, yet it has neither K5K_5K5 nor K3,3K_{3,3}K3,3 as a subgraph. (A graph that does contain one of them is nonplanar, as any graph with a nonplanar subgraph is.)
GGG : a path u,x,y,z,vu, x, y, z, vu,x,y,z,v , two adjacent vertices s,ts, ts,t each joined to all five path vertices, and the edge uvuvuv ( n=7n = 7n=7 , m=16m = 16m=16 ).Why does GGG have no K5K_5K5 subgraph?
A copy of K5K_5K5 would have to use uvuvuv , so three of its vertices would be adjacent to both uuu and vvv ; only sss and ttt are. It must use uvuvuv because G−uvG - uvG−uv is planar (in fact maximal planar). A similar case check on the partite sets rules out K3,3K_{3,3}K3,3 .
What is a subdivision of a graph GGG ?
GGG itself, or a graph obtained from GGG by inserting vertices of degree 2 into one or more edges. G1G_1G1 , G2G_2G2 and G3G_3G3 are subdivisions of GGG ; G2G_2G2 is also a subdivision of G1G_1G1 .
G′G'G′ is a subdivision of GGG . How is the planarity of G′G'G′ related to that of GGG ?
G′G'G′ is planar if and only if GGG is.
Kuratowski's Theorem (Theorem 9.7) A graph GGG is planar if and only if … ?
GGG does not contain a subdivision of K5K_5K5 or K3,3K_{3,3}K3,3 as a subgraph. The easy direction: such a subgraph is nonplanar. The book does not prove the converse.
What do you look for in GGG to find a subdivision of K5K_5K5 , or of K3,3K_{3,3}K3,3 , as a subgraph?
K5K_5K5 : 5 vertices of degree 4; K3,3K_{3,3}K3,3 : 6 vertices of degree 3, split into two sets of 3. They are joined (every pair, or every pair across the two sets) by paths whose interior vertices have degree 2. The degrees are taken in the subgraph.
Which degree condition on GGG guarantees, by Kuratowski's theorem, that GGG is planar?
At most four vertices of degree 4 or more, and at most five vertices of degree 3 or more. A subdivision of K5K_5K5 needs five vertices of degree at least 4, and one of K3,3K_{3,3}K3,3 needs six vertices of degree at least 3.
Is this graph planar? ( n=10n = 10n=10 , m=17m = 17m=17 .)
No: it contains a subdivision of K3,3K_{3,3}K3,3 as a subgraph. m=17≤24=3n−6m = 17 \le 24 = 3n - 6m=17≤24=3n−6 decides nothing. Only four vertices have degree 4 or more, so there is no subdivision of K5K_5K5 .
What is an embedding of a graph GGG in the plane?
A drawing of GGG in the plane with no two edges crossing. So GGG can be embedded in the plane exactly when it is planar, and likewise on the sphere.
What is the torus?
A doughnut-shaped surface. (b) and (c): two different embeddings of K4K_4K4 on the torus.
How is a torus built from a rectangle?
Identify opposite sides: glue one pair to make a cylinder, then glue its two end circles.
On the torus, drawn as a rectangle with opposite sides identified: can K5K_5K5 and K3,3K_{3,3}K3,3 be embedded?
Yes, both. (a) points with the same letter are the same point of the torus; (b) K5K_5K5 ; (c) K3,3K_{3,3}K3,3 .
How else can a torus be built from a sphere?
Drill two holes and attach a handle over them: a sphere with one handle is a torus. (c) K5K_5K5 on the torus, with one edge passing over the handle.
A sphere with kkk handles, denoted SkS_kSk , is called a surface of genus kkk .
S0S_0S0 is the sphere and S1S_1S1 is the torus.
Why can every graph be embedded on some surface?
Draw it on the sphere so that only two edges cross at each crossing point, then attach a handle at each crossing and pass one of the two edges over it.
What is the genus γ(G)\gamma(G)γ(G) of a graph GGG ?
The smallest k≥0k \ge 0k≥0 such that GGG can be embedded on SkS_kSk (the sphere with kkk handles). γ(G)=0\gamma(G) = 0γ(G)=0 if and only if GGG is planar. γ(K5)=γ(K3,3)=1\gamma(K_5) = \gamma(K_{3,3}) = 1γ(K5)=γ(K3,3)=1 .
When is a disconnected graph planar?
When every component is planar.
2K32K_32K3 (two disjoint triangles) is drawn as a plane graph. What is n−m+rn - m + rn−m+r (order, size, regions)?
6−6+3=3\boldsymbol{6 - 6 + 3 = 3}6−6+3=3 , not 2. No contradiction: the Euler Identity requires a connected graph.
GGG is embedded on a surface. How do you decide whether two points AAA and A′A'A′ lie in the same region?
Same region if and only if some curve on the surface joins AAA to A′A'A′ without meeting a vertex or an edge of GGG .
Do all embeddings of K4K_4K4 on the torus have the same number of regions?
No: there are embeddings with 4, 3 and 2 regions. So on the torus, n−m+rn - m + rn−m+r is not determined by the graph alone.
When is a region of an embedded graph a 2-cell, and what is a 2-cell embedding?
2-cell: every closed curve drawn in the region can be continuously contracted to a point within the region. 2-cell embedding: every region is a 2-cell.
Which embeddings in the plane are 2-cell embeddings?
Exactly the embeddings of connected graphs. No embedding of a disconnected graph in the plane is 2-cell. 2K32K_32K3 on the sphere: CCC shrinks to a point within its region, but C′C'C′ , around one triangle, does not.
Is every embedding of a connected graph on the torus a 2-cell embedding?
No. Two embeddings of K4K_4K4 : the curves CCC and C′C'C′ cannot be shrunk to a point within their regions. The 2-cell embedding of K4K_4K4 on the torus has 2 regions: 4−6+2=04 - 6 + 2 = 04−6+2=0 .
Theorem 9.9 A connected graph GGG of order nnn and size mmm is 2-cell embedded on a surface of genus k≥0k \ge 0k≥0 , with rrr regions. Then n−m+r= ?n - m + r = \; ?n−m+r=?
2−2k\boldsymbol{2 - 2k}2−2k For k=0k = 0k=0 this is the Euler Identity.
If a connected graph of order nnn and size mmm is 2-cell embedded on SkS_kSk (the sphere with kkk handles) with rrr regions, then n−m+r=2−2kn - m + r = 2 - 2kn−m+r=2−2k .How does the induction step from Sk+1S_{k+1}Sk+1 to SkS_kSk work?
Cut a handle along a closed curve CCC around it and patch the two holes; this raises n−m+rn - m + rn−m+r by exactly 2. First make the ttt points where CCC crosses edges into vertices, add 2 more vertices on CCC , and make the arcs of CCC edges: nnn , mmm , rrr grow by t+2t + 2t+2 , 2t+22t + 22t+2 , ttt , so n−m+rn - m + rn−m+r is unchanged. Cutting duplicates the t+2t + 2t+2 vertices and t+2t + 2t+2 edges on CCC and adds 2 regions. So (n−m+r)+2=2−2k(n - m + r) + 2 = 2 - 2k(n−m+r)+2=2−2k .
Corollary 9.10 A connected graph GGG of order nnn and size mmm is embedded on a surface of genus γ(G)\gamma(G)γ(G) (the genus of GGG ), with rrr regions. Then n−m+r= ?n - m + r = \; ?n−m+r=?
2−2γ(G)\boldsymbol{2 - 2\gamma(G)}2−2γ(G) An embedding of a connected graph on a surface of genus γ(G)\gamma(G)γ(G) is always a 2-cell embedding (stated in the book without proof).
Corollary 9.11 If GGG is a connected graph of order n≥3n \ge 3n≥3 and size mmm , then its genus satisfies γ(G)≥ ?\gamma(G) \ge \; ?γ(G)≥?
m6−n2+1\boldsymbol{\dfrac{m}{6} - \dfrac{n}{2} + 1}6m−2n+1 For planar GGG ( γ(G)=0\gamma(G) = 0γ(G)=0 ) this is m≤3n−6m \le 3n - 6m≤3n−6 again.
If GGG is a connected graph of order n≥3n \ge 3n≥3 and size mmm , then γ(G)≥m6−n2+1\gamma(G) \ge \frac{m}{6} - \frac{n}{2} + 1γ(G)≥6m−2n+1 .Why?
Embed GGG on a surface of genus γ(G)\gamma(G)γ(G) : every region has at least 3 boundary edges, so 3r≤2m3r \le 2m3r≤2m ; insert this into n−m+r=2−2γ(G)n - m + r = 2 - 2\gamma(G)n−m+r=2−2γ(G) . 6−6γ(G)=3n−3m+3r≤3n−3m+2m=3n−m6 - 6\gamma(G) = 3n - 3m + 3r \le 3n - 3m + 2m = 3n - m6−6γ(G)=3n−3m+3r≤3n−3m+2m=3n−m .
If GGG is a connected graph of order n≥3n \ge 3n≥3 and size mmm , then γ(G)≥m6−n2+1\gamma(G) \ge \frac{m}{6} - \frac{n}{2} + 1γ(G)≥6m−2n+1 .What lower bound does this give for the genus of K7K_7K7 ?
γ(K7)≥1\boldsymbol{\gamma(K_7) \ge 1}γ(K7)≥1 n=7n = 7n=7 , m=21m = 21m=21 : 216−72+1=1\frac{21}{6} - \frac{7}{2} + 1 = 1621−27+1=1 . In fact γ(K6)=γ(K7)=1\gamma(K_6) = \gamma(K_7) = 1γ(K6)=γ(K7)=1 .
Theorem 9.12 (Ringel and Youngs) For n≥3n \ge 3n≥3 , the genus of the complete graph is γ(Kn)= ?\gamma(K_n) = \; ?γ(Kn)=?
⌈(n−3)(n−4)12⌉\boldsymbol{\left\lceil \dfrac{(n-3)(n-4)}{12} \right\rceil}⌈12(n−3)(n−4)⌉ e.g. γ(K5)=⌈2/12⌉=1\gamma(K_5) = \lceil 2/12 \rceil = 1γ(K5)=⌈2/12⌉=1 , γ(K8)=⌈20/12⌉=2\ \gamma(K_8) = \lceil 20/12 \rceil = 2 γ(K8)=⌈20/12⌉=2 .
What does it mean to contract the edge e=uve = uve=uv of a graph GGG ?
Delete vvv and join uuu to every neighbor of vvv not already adjacent to uuu . Also called identifying the vertices uuu and vvv , or an edge contraction. G′G'G′ : contract uvuvuv in GGG . G′′\ G'' G′′ : contract xyxyxy in G′G'G′ .
How can the graph obtained from GGG by a sequence of edge contractions be described in one step?
Partition V(G)V(G)V(G) into sets V1,…,VkV_1, \dots, V_kV1,…,Vk that each induce a connected subgraph. HHH has vertices V1,…,VkV_1, \dots, V_kV1,…,Vk , with ViVjV_i V_jViVj an edge when some vertex of ViV_iVi is adjacent to some vertex of VjV_jVj . V1={x,y}V_1 = \{x, y\}V1={x,y} , V2={z}V_2 = \{z\}V2={z} , V3={u,v}V_3 = \{u, v\}V3={u,v} , V4={t}V_4 = \{t\}V4={t} , V5={w}V_5 = \{w\}V5={w} .
When is a graph HHH a minor of a graph GGG ?
(A graph isomorphic to) HHH can be obtained from GGG by a succession of edge contractions, edge deletions and vertex deletions, in any order. Contracting each dotted set of G1G_1G1 gives H1H_1H1 ; deleting the edge V1V2V_1V_2V1V2 and the vertex V7V_7V7 then gives K3,3K_{3,3}K3,3 .
GGG is a subdivision of HHH . What relation does HHH have to GGG , and why?
HHH is a minor of GGG . Contract one edge at each inserted vertex of degree 2.
HHH is a minor of GGG . How do their genera γ(H)\gamma(H)γ(H) and γ(G)\gamma(G)γ(G) compare?
γ(H)≤γ(G)\boldsymbol{\gamma(H) \le \gamma(G)}γ(H)≤γ(G) If GGG embeds on SkS_kSk , so does every graph obtained from GGG by an edge contraction, edge deletion or vertex deletion.
Wagner's Theorem (Theorem 9.15) A graph GGG is planar if and only if … ?
Neither K5K_5K5 nor K3,3K_{3,3}K3,3 is a minor of GGG . Klaus Wagner, 1937, a year after his Ph.D. at the University of Cologne.
This graph contains no subdivision of K5K_5K5 . Is K5K_5K5 a minor of it?
Yes. Contract V1={u1,v1,w1,x1,y1}V_1 = \{u_1, v_1, w_1, x_1, y_1\}V1={u1,v1,w1,x1,y1} (the outer cycle) and V3={u2,y2}V_3 = \{u_2, y_2\}V3={u2,y2} ; keep V2={v2}V_2 = \{v_2\}V2={v2} , V4={w2}V_4 = \{w_2\}V4={w2} , V5={x2}V_5 = \{x_2\}V5={x2} . So by Wagner's theorem the graph is nonplanar.
The Graph Minor Theorem (Robertson and Seymour) For any infinite set SSS of graphs, … ?
There are two distinct graphs in SSS such that one is a minor of the other. Neil Robertson and Paul Seymour, 1990 according to the book.
When is a graph FFF minimally nonembeddable on SkS_kSk (the sphere with kkk handles)?
FFF cannot be embedded on SkS_kSk , but every edge contraction, edge deletion or vertex deletion of FFF can. So every minor of FFF other than FFF embeds on SkS_kSk . On S0S_0S0 this is called minimally nonplanar.
Which graphs are minimally nonplanar (nonplanar, but every edge contraction, edge deletion or vertex deletion is planar)?
Exactly K5K_5K5 and K3,3K_{3,3}K3,3 .
Theorem 9.17 For each integer k≥0k \ge 0k≥0 , the set of minimally nonembeddable graphs on SkS_kSk (the sphere with kkk handles) is … ?
Finite. For the torus, the set is known to have more than 800 graphs.
Graph Minor Theorem: every infinite set of graphs contains two distinct graphs, one a minor of the other.Why is the set of minimally nonembeddable graphs on SkS_kSk finite?
If it were infinite, one of its graphs HHH would be a minor of another one GGG ; but every minor of GGG other than GGG embeds on SkS_kSk , and HHH does not.
Corollary 9.18. What characterization of the graphs embeddable on SkS_kSk (the sphere with kkk handles) follows from the Graph Minor Theorem?
There is a finite set SSS of graphs such that GGG embeds on SkS_kSk if and only if no graph in SSS is a minor of GGG . For k=0k = 0k=0 , S={K5,K3,3}S = \{K_5, K_{3,3}\}S={K5,K3,3} by Wagner's theorem.
What does it mean that a graph GGG is embedded in a graph HHH ?
GGG is (isomorphic to) an induced subgraph of HHH .
König: for r=Δ(G)r = \Delta(G)r=Δ(G) , take a copy G′G'G′ of GGG and join corresponding vertices of degree less than rrr ; repeat until the graph is rrr -regular. The result contains GGG as an induced subgraph.How many rounds does this take, and does it give an rrr -regular graph of smallest order?
Δ(G)−δ(G)\Delta(G) - \delta(G)Δ(G)−δ(G) rounds; in general not of smallest order. Here Δ(G)=3\Delta(G) = 3Δ(G)=3 , δ(G)=1\delta(G) = 1δ(G)=1 : HHH has order 16, while the minimum order of a 3-regular graph containing GGG as an induced subgraph is 6.
GGG has maximum degree rrr and vertices v1,…,vnv_1, \dots, v_nv1,…,vn of degrees d1,…,dnd_1, \dots, d_nd1,…,dn . What are the deficiency eie_iei of viv_ivi , the maximum deficiency eee and the total deficiency sss ?
ei=r−di\boldsymbol{e_i = r - d_i}ei=r−di , e=max⁡ei\ e = \max e_i e=maxei , s=∑ei\ s = \sum e_i s=∑ei .
Theorem 9.19 (Erdős and Kelly, 1963) GGG has order nnn , r=Δ(G)r = \Delta(G)r=Δ(G) , total deficiency s=∑(r−deg⁡v)s = \sum (r - \deg v)s=∑(r−degv) and maximum deficiency eee . What is the minimum order of an rrr -regular graph containing GGG as an induced subgraph?
n+k\boldsymbol{n + k}n+k , for the least integer kkk with kr≥skr \ge skr≥s , k2−(r+1)k+s≥0\ k^2 - (r+1)k + s \ge 0 k2−(r+1)k+s≥0 , k≥e\ k \ge e k≥e and (k+n)r(k + n)r(k+n)r even.
Erdős–Kelly: for GGG of order nnn , r=Δ(G)r = \Delta(G)r=Δ(G) , total deficiency sss and maximum deficiency eee , the minimum order of an rrr -regular graph containing GGG as an induced subgraph is n+kn + kn+k , for the least kkk with kr≥skr \ge skr≥s , k2−(r+1)k+s≥0k^2 - (r+1)k + s \ge 0k2−(r+1)k+s≥0 , k≥ek \ge ek≥e and (k+n)r(k + n)r(k+n)r even. GGG is a triangle with a pendant edge (degrees 3, 2, 2, 1). What is that minimum order?
6 r=3r = 3r=3 ; deficiencies 0,1,1,20, 1, 1, 20,1,1,2 , so s=4s = 4s=4 , e=2e = 2e=2 . Then 3k≥43k \ge 43k≥4 and k≥2k \ge 2k≥2 ; k2−4k+4=(k−2)2≥0k^2 - 4k + 4 = (k-2)^2 \ge 0k2−4k+4=(k−2)2≥0 always; (k+4)⋅3(k + 4) \cdot 3(k+4)⋅3 even needs kkk even. So k=2k = 2k=2 .
When is a graph GGG uniformly embedded in a graph HHH ?
Every vertex of HHH lies in an induced subgraph of HHH isomorphic to GGG . König's rrr -regular graph, built from copies of GGG , always has this property.
HHH is an rrr -regular graph of minimum order containing GGG as an induced subgraph, where r=Δ(G)r = \Delta(G)r=Δ(G) . Is GGG always uniformly embedded in HHH (every vertex of HHH in an induced copy of GGG )?
No. GGG : K3,3K_{3,3}K3,3 with two edges subdivided (order 10). HHH : 3-regular of minimum order 12, but no induced copy of GGG in HHH contains uuu .
When is a graph GGG homogeneously embedded in a graph HHH ?
For every vertex xxx of GGG and every vertex yyy of HHH , there is an embedding of GGG in HHH as an induced subgraph with xxx at yyy . That is, an induced subgraph H′H'H′ of HHH and an isomorphism ϕ:G→H′\phi: G \to H'ϕ:G→H′ with ϕ(x)=y\phi(x) = yϕ(x)=y .
What is a frame of a graph GGG , and its framing number fr⁡(G)\operatorname{fr}(G)fr(G) ?
A frame is a graph of minimum order in which GGG can be homogeneously embedded; fr⁡(G)\operatorname{fr}(G)fr(G) is its order. So fr⁡(G)≥n\operatorname{fr}(G) \ge nfr(G)≥n for GGG of order nnn .
What is the framing number fr⁡(P3)\operatorname{fr}(P_3)fr(P3) (least order of a graph in which P3P_3P3 is homogeneously embedded)?
4, with frame C4C_4C4 . Any 3 vertices of C4C_4C4 induce P3P_3P3 , so any vertex of P3P_3P3 can be put at any vertex of C4C_4C4 . Order 3 fails: the only candidate is P3P_3P3 itself, where an end-vertex can't be placed at the center.
What is the framing number fr⁡(K1∪K2)\operatorname{fr}(K_1 \cup K_2)fr(K1∪K2) (least order of a graph in which K1∪K2K_1 \cup K_2K1∪K2 is homogeneously embedded)?
4, with frame 2K22K_22K2 . K1∪K2K_1 \cup K_2K1∪K2 is also homogeneously embedded in C5C_5C5 . Order 3 fails: the only candidate is K1∪K2K_1 \cup K_2K1∪K2 itself, where the isolated vertex can't be placed at an end of the edge.
GGG is homogeneously embedded in HHH . How do δ(H)\delta(H)δ(H) and Δ(G)\Delta(G)Δ(G) compare, and why?
δ(H)≥Δ(G)\boldsymbol{\delta(H) \ge \Delta(G)}δ(H)≥Δ(G) A vertex of maximum degree in GGG can be placed at any vertex of HHH .
GGG is K4K_4K4 minus an edge (vertices u,vu, vu,v of degree 2, and w,xw, xw,x of degree 3). What is its framing number fr⁡(G)\operatorname{fr}(G)fr(G) ?
6, with frame K2,2,2K_{2,2,2}K2,2,2 (the octahedron). A frame HHH has δ(H)≥3\delta(H) \ge 3δ(H)≥3 . Order 5 fails: the new vertex must be adjacent to uuu and vvv (to give them degree 3) and, having degree at least 3, to xxx (say), so xxx is adjacent to all other vertices and has degree 3 in every induced 4-vertex subgraph; uuu can't be placed there.
Does every graph have a framing number (a graph in which it is homogeneously embedded)? What more is true?
Yes: every graph can be homogeneously embedded in some graph, and even in some regular graph.