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?
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.