0
$\begingroup$

Let $G_{w}$ be the set of all weighted graphs $(G,f)$ with $G = (V,E)$, $V = \{1,...,n\}$ for an $n \in \mathbb N$ and $f: E \to \mathbb N$ the weight function. I need to prove or disprove that the set is countable.

This is how I proceeded:

assume that $G_{w}$ is countable, then we can make a list of all the graphs in the set, so an injection $G_{w} \to \mathbb N$. Let now $G_{n}$ be the n-th graph in the list. We construct a new weighted graph $G'_{n} = (V',E')$

$V' = V + \{ v_{new}\}$

$E' = E + \{v_{new},u\}$

$f'(\{v_{new},u\}) = m$ for some number $m \in \mathbb N$

this new graph is obvoiusly also in $G_{w}$ but not in our list per construction. So we arrive at a contradiction and therefore the set $G_{w}$ is not countable.

is this proof correct? please help I'm not sure. I also had the idea of trying to construct a similar proof with the set of all possible wight functions f. Since f is injective and the edge set is always finite, I was not sure if the set of all the weight functions is also uncountable.

Thank you for your help

Alternative idea:

We know that the set of all possible edges between finitely many verices is countable. Since for each vertex from the finite set $\{1,...,n\}$ we assign it to a vertex from the finite set $\{1,...,n\}$. So the set of all possible edges is countable since we have a bijection. Now for each edge, we assign a number to it via a weighting function $f$. There are countable many such possible weightings. A function $f: E \to \mathbb N$ is injective.

so in total we have countable many possibilities, hence the set $G_{w}$ is countable.

$\endgroup$
6
  • $\begingroup$ Why is it not in your list per construction? And what makes you so sure that the set is uncountable? $\endgroup$
    – Servaes
    Jul 5, 2017 at 7:26
  • $\begingroup$ this is the point that I struggle with. I assumed that the next graph $G_{n+1}$ be different than the constructed one. $\endgroup$ Jul 5, 2017 at 7:28
  • $\begingroup$ Sure it is different if you construct it properly. But why would that mean it isn't in the list? $\endgroup$
    – Servaes
    Jul 5, 2017 at 7:30
  • $\begingroup$ Hmm I guess you're right and that's the sticking point in my proof. an alternative idea: what if we know that the set of all possible edges is countable, since we have a function $\{1,...,n\} \to \{1,...,n\}$ which is countable and we have countable many functions f that assign a number to the countable many edges, so in total the set is countable. I'm really confused at this point... $\endgroup$ Jul 5, 2017 at 7:33
  • $\begingroup$ I would suggest to first prove that a countable union of countable sets is again countable. This is proved in any basic textbook on set theory, and makes your problem very easy. $\endgroup$
    – Servaes
    Jul 5, 2017 at 8:37

2 Answers 2

4
$\begingroup$

As far as I understand, you're simply adding a new weighted edge between a new vertex and some other vertex in the $G_n$. There is no reason this graph cannot be in your list.

In any case, the set is countable, assuming your graphs are simple. There are finitely many simple graphs of $n$ vertices for every $n \in \mathbb{N}$, and for each graph countably many weighting functions. So you get a countable union of countable sets, which is countable.

$\endgroup$
1
$\begingroup$

Your proof is incorrect because you did not prove that $V'$ is not in the original list.


To actually solve the problem, here's two facts to think about:

  1. A countable union of countable sets is countable.
  2. For each $n$, the set of all weighted graphs on $\{1,2,\dots, n\}$ is countable because you can construct a bijection from it onto $\mathbb N^{n\choose 2}$
$\endgroup$
4
  • $\begingroup$ Thank you for the clarification. An alternative idea that I also posted above.: what if we know that the set of all possible edges is countable, since we have a function {1,...,n}→{1,...,n} which is countable and we have countable many functions f that assign a number to the countable many edges, so in total the set is countable. $\endgroup$ Jul 5, 2017 at 7:37
  • $\begingroup$ @user3047143 I don't know what "a function {1,...,n}→{1,...,n}{1,...,n}→{1,...,n}" means. Rather than typing out the answer in a comment, I suggest you edit your original question and coherently weite out this alternative idea. $\endgroup$
    – 5xum
    Jul 5, 2017 at 7:38
  • $\begingroup$ My bad it was a typo $\endgroup$ Jul 5, 2017 at 7:40
  • $\begingroup$ @user3047143 I think you should write this alternative idea out in full before I can comment it. $\endgroup$
    – 5xum
    Jul 5, 2017 at 7:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .