1
$\begingroup$

I am new to graph theory and I would like to have some insight into a method on how to solve questions like this.

Given a simple planar graph in a sphere satisfying the conditions that:

  1. Each vertex has degree five.
  2. Each face is either a triangle or a pentagon.
  3. Each pentagon shares edges with five triangles.
  4. Triangles are divided into Type I: sharing edges with one pentagon and two triangles, and Type II: sharing edges with three triangles.
  5. Each Type I triangle shares edges with one pentagon and two Type II triangles, and each Type II triangle shares edges with one Type I triangle and two Type II triangles.

Find the number of vertices, edges, and faces respectively for the graph.

$\endgroup$
1
$\begingroup$

Define the number of vertices, edges, faces to be $V,E,F$. We can further split $F=P+T$, where $P$ is the number of pentagons and $T$ the number of triangles, and further still $T=T_1+T_2$ where $T_1$ is the number of triangles of type I and $T_2$ the number of type II.

There are three equations we can get using common, textbook arguments and $(1),(2)$:

  • Euler's formula says $V-E+F=2$.
  • If you sum all the vertex degrees you double-count each edge, so $2E=5V$.
  • Summing edge counts of all faces again double-counts edges, so $2E=5P+3T$.

Solve for $E$ then $V$ in terms of $P,T$, plug into Euler's, get a linear equation in $P,T$.

Similar logic can be used with conditions $(3),(4),(5)$:

  • Since type II triangles are not incident to pentagons, each pentagon is incident to $5$ type I triangles; use this to triple-count type I triangles in terms of $P$ and $T_2$.

  • Similarly, we can triple-count type II triangles in terms of $T_1$ and $T_2$.

Use the latter to find a nice relationship between $T_1,T_2$ and plug into the former to relate to $P$, then go back to readdress the original linear equation involving $P$ and $T$.

$\endgroup$
6
  • $\begingroup$ Could you explain the part about triple counting more please? $\endgroup$ – random1234 May 28 '20 at 9:15
  • $\begingroup$ @random1234 Do you understand the equations I mentioned for double-counting edges? The idea is that if each vertex declares the edges it's adjacent to (or if each face declares the edges it's adjacent to) each edge will wind up counted twice. Well, now let's say we want each face to declare e.g. how many type II triangles it's incident to... you'd wind up counting each type II triangle thrice, right? $\endgroup$ – runway44 May 28 '20 at 9:17
  • 1
    $\begingroup$ Yes I understand the equation for double counting. So as I understand now If each type I triangle shares edges with one pentagon and two type II triangles then 3*T1 = 2*T2 + 5*P and similarly 2*T2 + T1 = 3*T2 ? $\endgroup$ – random1234 May 28 '20 at 10:19
  • $\begingroup$ In my now-deleted comment I had misread your equations since your left/right sides are switched from mine. In any case, I think you have some coefficients swapped. For example, for triple-counting type I triangles, imagine each face is casting a "vote" for each incident type I triangle. Then $3T_1$ counts the total received votes, whereas the total submitted votes ought to be $5P+\color{Red}{1}T_2$ (as each type II triangle is only incident to a single type I triangle to cast the vote to). And similar for triple-counting type II triangles. $\endgroup$ – runway44 May 28 '20 at 10:31
  • 1
    $\begingroup$ I see. So for the second equation it would be 3*T2 = 0*P + 2*T1 + 2*T2 (since pentagon submits 0 votes for T2 and T1, T2 both submit 2)? $\endgroup$ – random1234 May 28 '20 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.