I will solve a graph theory problem:
Let G be a connected 3-regular plane graph in which every vertex lies on one face of length 4, one face of length 6, and one face of length 8.
(a) In terms of n(G), determine the number of faces of each length.
(b) Use Euler’s Formula and part(a) to determine the number of faces of G.
Graph Theory Problem Solving:
Let $e=e(G)$, $n=n(G)$ and $f$ be the number of faces from the graph $G$. Since $G$ is a 3-regular graph, $2e=3n$. For each $i \in \{4,6,8\}$, let $f_i$ be the number of faces whose length is $i$. Each vertex lies on one face of length $i$, for all $i\in \{4,6,8\}$. Therefore $n=if_i$ for all $i \in \{ 4,6,8\}$. Therefore, $f_i = \frac{n}{i}$ for all $i \in \{4,6,8\}$. By Euler’s formula $n-e+f=2$. Therefore, $n- \frac{3}{2} n + \sum_{i \in \{4,6,8\}} n/ i =2$. Therefore, $n=48$. From the relation $n=if_i$, $f_4=12$, $f_6=8$ and $f_8=6$.
Related Posts:
[Graph Theory problem solving]For n ≥ 1, let Gn = Pn□K2 ; this is the graph with 2n vertices and 3n − 2 edges shown below. Determine χ(Gn; k). (You should simplify your answer by factoring the polynomial
[Graph Theory problem solving] Prove that if G is a color-critical graph, then the graph G′ generated from it by applying Mycielski’s construction is also color-critical. (If χ(H) < χ(G) for every proper subgraph H of G, then G is called color-critical.)
[Graph Theory problem solving] Prove that a graph G is m-colorable if and only if α(G□Km) ≥ n(G).
[Graph Theory problem solving] Deduce that $e(T_{n,k}) = \left \lfloor \left(\frac{k-1}{2k} \right) n^2\right \rfloor$ for all $k < 8$
[Graph Theory problem solving] Show that $(\frac{k-1}{2k})n^2 – \frac{1}{8 k} \leq e (T_{n,k}) \leq (\frac{k-1}{2k}) n^2$.
[그래프이론 (Graph Theory) 문제풀이] The Turan graph T_{n,r} is the compelete r-partite graph with b partite sets of size a+1 and r − b partite sets of size a, where a = \lfloor n/r\rfloor and b = n − ra. (a) Prove that e(T_{n,r}) =\left( 1- \frac{1}{r} \right)\frac{n^2}{2} - \frac{b(r-b)}{2r} . (b) Since e(G) must be an integer, part (a) imples e(T_{n,r}) ≤ \lfloor (1-\frac{1}{r}) \frac{n^2}{2} \rfloor Determine when strict inequality occurs
Source: Homework problem from Professor Choi‘s Graph Theory class, Gwangju Institute of Science and Technology, Fall Semester 2023