Discrete math ( graphs, trees and tours)

49 Views Asked by At

Can someone check with me if my answer is right for this question? I got $n(n+1)/2$ . The question is posted below. $\newcommand{\Barbell}{\operatorname{Barbell}}$

For $n$ an integer with $n ≥ 3$, let $\Barbell(n)$ be the graph that is made by attaching with a single edge two complete graphs with $n$ vertices each. A complete graph with $n$ vertices is a graph in which every vertex is adjacent to every other vertex besides itself. The following question is about $\Barbell(n)$. For an integer $n ≥ 3$, how many edges are in the graph $\Barbell(n)$?

1

There are 1 best solutions below

2
On

To clarify, given $n\geq 3$ you are given two graphs $G_{1}$ and $G_{2}$, each of which is a copy of the complete graph on $n$ vertices, $K_{n}$. The graph Barbell$(n)$ is then formed by choosing a vertex $v_{1}\in G_{1}$ and a vertex $v_{2}\in G_{2}$ and then adding an edge between $v_{1}$ and $v_{2}$ to connect $G_{1}$ and $G_{2}$ together.

Hint:

How many edges are in $K_{n}$?

$K_{2}$ has $1$ edge.

$K_{3}$ has $3$ edges.

$K_{4}$ has $6$ edges.

In general there are as many edges in $K_{n}$ as there are ways of choosing a subset of size $2$ out of the set $\{1,2,\ldots,n\}$.

If the number of edges in $K_{n}$ is $E(n)$ then the answer to your problem is $2E(n)+1$.