My question is based on information that you are asked to deduce for yourself to confidently answer question #10 of Ralph P. Grimaldi's Discrete and Combinatorial Mathematics An Applied Introduction (5th Edition).
The question is:
The connected undirected graph $G=(V,E)$ has 30 edges. What is the maximum value that $|V|$ can have?
From what is written in the text I can sort of deduce that Theorem 12.3:
In every tree $T=(V,E), |V|=|E|+1$
will have something to do with it. However I would need to deduce that $G$ is a tree first.
My idea is to use the fact that if $G$ is planar and connected, then $v-e+r=2$ where $|V|=v$ and $|E|=e$ and $r$ is the number of regions made by the planar graph. To maximize $v$, minimize $r$. The smallest $r$ can be is 1 (zero inner regions, there is always 1 outer region). Then $v=e+2-1=e+1.$
If G is connected and nonplanar, then remove as many edges as necessary to make G planar. $|E|=30-k$ for our particular example, however we can make $|E|$ arbitrary. Then again, $v=e-k+2-1=e-k+1,$ for $k\geq1$, thus $v$ is smaller.
Since $G$ can be connected and either planar or nonplanar, the maximum number of $|V|$ is $|E|+1.$ And $G$ being connected and having $|V|=|E|+1$ is equivalent to $G$ being a tree.
Am I on the right track? Or are my assumptions about planar and nonplanar too swift?
Best Answer
The planarity seems irrelevant for the problem, but here is one way to look at it:
Given $m$ "vertex-less" edges you can add at most $2m$ vertices (-> $m$ disjoint edges) but you want to maximize $|V|$ while staying connected. Look at it as an algorithm, a step by step process of adding vertices. For the first edge, you have no choice but to give it $2$ vertices. For the second edge you have to add at least one vertex to it (supposing multiple edges are forbidden), but adding $2$ would produce a disjoint edge. For all the subsequent edges, you can add between $0$ and $2$ vertices to each edge. Adding $2$ is illegal because it disconnects the graph, adding $1$ is possible at each step, so you do it (you want to maximize $|V|$).
This produces $2+(m-1)\cdot1=m+1$ vertices.