1

Assume $G$ is a connected planar graph with 100 edges. While the edges can be split into two sets, $S_1$ and $S_2$ such that $|S_1|=60$ and $|S_2|=40$. Given that for all $e$ in $S_1$, the face on one side of $e$ has 3 edges, and the face on the other side has 10 edges. Also, for all $e$ in $S_2$, the two faces on each side of $e$ are distinct from each other and both have 10 edges.

Then, How many vertices does G have?

I guess this question can be solved by Euler's formula in planar graph that $"V-E+F=2"$. However, I do not know how to calculate the number of faces in the graph.

Anyone can give me some hints for solving this questions? Thanks!

Vincent
  • 13
  • Some hints: (1) If you replaced "faces" with "vertices" in the description, this would be solvable for any graph, planar or not, connected or not, that did not have vertices with no edges. It has nothing to do with Euler's formula. (2) it does have to do with the degrees of the faces (how many edges border them). (3) instead of counting edges, count "edge sides", which only touch one face, not two. But keep in mind which set each edge-side came from. – Paul Sinclair Nov 21 '21 at 18:54
  • @PaulSinclair But how do I count the degrees of the faces if the faces for some $e$ may be overlapped. Can you give some examples? – Vincent Nov 22 '21 at 08:07
  • First let me correct part of the previous comment. I was thinking of counting faces only. In order to find the number of vertices from the number of faces, you do need Euler's formula. Now, what "overlap" are you talking about? Every face has edges bordering it. Every edge borders two faces. From the information given, every edge is either between a degree-3 face and degree 10-face, or between two degree-10 faces. Thus every face has degee 3 or degree 10. Now let $m$ be the number of degree-3 faces and $n$ be the number of degree-10 faces. What equations do you get? – Paul Sinclair Nov 22 '21 at 13:26
  • If you are worried about bridges - edges whose removal would disconnect the graph, having the same face on each side - I am sure that when they say a face has 3 or 10 edges, they are counting any bridges twice, once for each incidence of it bordering the face. This is like when one says an $n$-degree polynomial has $n$ complex roots: you count the roots by multiplicity, not distinct values. So the same goes for counting edges around faces or vertices. Certainly I meant as such in my comments. – Paul Sinclair Nov 22 '21 at 16:51
  • Since sum of degrees of all faces equal to $2Edges$, Then for $S_1$, $"3m + 10n = 60 2"$ and For $S_2$, $"10k + 10k = 40 * 2"$, where $k$ is the number of degree-10 faces in $S_2$. Is my approach correct? It seems that I cannot solve the first equation for $S_1$, is there any relationship between $k$ and $n$? – Vincent Nov 23 '21 at 09:23
  • No. Neither of those equations are correct. In fact, they don't seem to make any sense. $S_1$ and $S_2$ are collections of edges, not faces. There is no such thing as "degree-10 faces in $S_2$". The edges in $S_2$ run between degree-10 faces, but those faces may also have edges that are in $S_1$, so you cannot divide the faces between $S_1$ and $S_2$. And $3m + 10n$ is the sum of the degrees of all faces in the graph, So it counts all "edge sides", not just the ones in $S_1$. I.e. $3m+10n = 200$, not $120$. – Paul Sinclair Nov 23 '21 at 13:26
  • However, you can divide the edge-sides around the degree-3 faces between $S_1$ and $S_2$, and similarly for the edge-sides around the degree-10 faces. – Paul Sinclair Nov 23 '21 at 13:29
  • So the number of edges for all degree-3 faces is $3m/2$, number of edges for all degree-10 faces is $5n$. But how do I count the exact edge-sides around the degree-10 faces if that faces contains both edges from $S_1$ and $S_2$? – Vincent Nov 24 '21 at 06:58
  • First, let me re-iterate: Count edge-sides, not edges. Edge-sides are associated with only one face, not two. Second, go look at the definitions of $S_1$ and $S_2$ again. How are the degree-3 edge-sides distributed between them? How about the degree-10 edge-sides? – Paul Sinclair Nov 24 '21 at 13:59
  • Since each edge in degree-3 faces must be surrounded by three degree-10 faces, then $m = 3n$, so $30n + 10n = 200$ and $n = 5$, $m = 50$. Is it correct? I am so confused that how to find number of degree-3 face from the information given. – Vincent Nov 26 '21 at 03:41
  • Why do you think every degree-10 face has 3 triangles bordering only it?? How does that make any sense? Why are you bound and determined to pull a direct relationship between the number of degree-3 and degree-10 faces, while ignoring what i've told you repeatedly to do: count edge-sides? The information given to you was the number of edges in each of two groups. You've completely ignored that information to make wild guesses instead. How many degree-3 edges are in $S_1$? How many degree-3 edges are in $S_2$? – Paul Sinclair Nov 26 '21 at 04:05

1 Answers1

3
  • Because the edges in $S_1$ and $S_2$ are disjoint, and there are $100$ edges in total, we know that every edge is in either $S_1$ or $S_2$.
  • Thus every face is either of degree $3$ or degree $10$.
  • We can consider splitting each edge into two sides, one for each face it touches. You can think of this as cutting the plane up into pieces along the edges. Each side is the resulting boundary segment of one of the faces.
  • Each side is in contact with exactly one face, so a face of degree $3$ has $3$ sides unique to it, and each face of degree $10$ has $10$ sides unique to it.
  • Each edge in $S_1$ has two sides, one of which is for a degree $3$ face, and the other for a degree $10$ face. Since there are $60$ edges in $S_1$ that provides $60$ degree-$3$ sides and $60$ degree-$10$ sides.
  • Each edge in $S_2$ has two degree-$10$ sides. Since there are $40$ edges, that provides $80$ degree-$10$ sides.

Altogether, there are $60$ degree-$3$ sides and $60 + 80 = 140$ degree-$10$ sides. Now as each degree-$3$ face is surrounded by $3$ degree-$3$ sides, there has to be $20$ of them. And each degree-$10$ face is surrounded by $10$ degree-$10$ sides, so there has to be $14$ of them.

Hence your graph has a total of $34$ faces, and $2+100 - 34 = 68$ vertices.

Paul Sinclair
  • 43,643
  • For the final answer, do I need to count the outer region so that total region or faces becomes $34 + 1$ in the Euler’s formula? – Vincent Nov 28 '21 at 01:58
  • Actually I have think of a way to count number of degree-3 faces that $m = 60/3$ since each edge in $S_1$ must be a side of the degree-3 face. Then I can get the number of degree-10 faces by the formula $3m + 10n = 200$. – Vincent Nov 28 '21 at 02:07
  • The "outer region" is a face and has already been counted. Just like all the other faces, it is one side of each of the outside edges, and therefore has to be one of the degree-3 or degree-10 faces that border every edge. Your "way to count number of degree-3 faces" is exactly what I did above. The other formula can be used to get the degree-10 faces just as well as the way I did it. $S_2$ and its count had to be included in the problem statement so that we knew that all faces are degree-3 or degree-10. But once you know that, either way works. – Paul Sinclair Nov 28 '21 at 04:05