0
$\begingroup$

Let $G_{w}$ be the set of all wighted graphs $(G,f)$ with $G = (V,E)$, $V = \{1,...,n\}$ for an $n \in \mathbb N$ and $f: E \to \mathbb N$ the wight 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$ 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$ 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$ 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.