4
$\begingroup$

A connected graph is a graph with no disjoint subgraphs. A simple graph is a graph with no loops or multiple edges.

Easy Question: What are the necessary and sufficient conditions on the order (number of vertices) and size (number of edges) of a given graph in order to ensure that it is simple and connected?

For example, the only simple and connected graph of order $2$ and size $1$ is the path graph $P_2$ (a line segment). There is no simple and connected graph of order $2$ and size greater than or equal to $2$. A graph with order and size both $3$ is the cycle graph of order $3$ (a triangle). There is no simple and connected graph of order $3$ and size greater than or equal to $4$. Continuing in this fashion, I conclude that there must be a condition on the difference between the size and order (compared to the size).

Harder Question: For any pair of positive integers $(a,b)$ is there a simple and connected graph $G_{ab} = (V_{ab}, E_{ab})$ with order $|V_{ab}| = \frac{1}{2}(ab + a + b + \text{gcd}(a,b))$ and size $|E_{ab}| = ab$? If so, are such graphs significant?

For instance, if $b = 1$, then $|V_{ab}| = a + 1$, $|E_{ab}| = a$ and $G_{ab}$ can be realized as the path graph $P_{a+1}$ (or any tree with the same order), which is both simple and connected.

  • 0
    @joriki: Thanks for $t$he comment. I edited and clarified the harder question.2011-04-22

1 Answers 1

5

Easy Question:

Suppose that $|V|=n$. Then the graph cannot be simple if $|E|>\binom{n}{2}$ since the complete graph on $n$ vertices has $\binom{n}{2}$ edges. The graph cannot be disconnected if it is simple and $|E|>\binom{n-1}{2}$. This is because the complete graph on $n-1$ vertices has $\binom{n-1}{2}$ edges. (See this MSE thread for a discussion and a proof.) Note that for the connectedness requirement we must assume the graph is simple, otherwise we could just put all the edges between two vertices.

Harder Question: The answer is yes. We will prove that this graph has more edges then the tree on $|V|$ vertices, and less edges then the complete graph on $|V|$ vertices. (This means we can choose it to be simple and connected)

More than Tree:

Suppose $a\geq b$, and note that then $b\geq 1$, and if $b\neq 1$ we have $a\geq 2$. Also, $\gcd(a,b)\leq b$ so that $ |V|\leq \frac{1}{2}\left( ab+2b+a\right).$ It then follows that $|E|-|V|\geq ab- \frac{1}{2}\left( ab+2b+a\right)$ $=\frac{1}{2}\left(ab-2b-a+2\right)-1=\frac{1}{2}(a-2)(b-1)-1\geq -1.$ Consequently $|E|-|V|\geq -1$ so we have enough edges to connect the graph, as the connected tree on $|V|$ vertices has $|V|-1$ edges.

Less than Complete Graph:

We also do not have too many edges since $\gcd(a,b)\geq 1$ implies $\frac{1}{2}\left( ab+b+a+1\right)\leq |V|.$ This means $|E|+b+a+1\leq2|V|,$ and since $b\geq 1$, $a\geq1$ we have $|E|\leq 2|V|-3$. But since $n^2-5n+6\geq 0$ for integers $n\geq 1$ we see that $\frac{n^2-n}{2}\geq 2n-3$ and hence $2n-3\leq\binom{n}{2}$ for every positive integer $n$. Consequently, $|E|\leq 2|V|-3$ implies that $|E|\leq \binom{|V|}{2}$ so that the graph has less edges then the complete graph, and can be chosen to be simple.

Hope that helps,

  • 1
    @User02138: I edited again to clean up the last argument so it no longer requires chec$k$i$n$g particular cases.2011-04-22