Proof, that there is a subset of vertices, which form a connected graph.

Question

The following question seems to be quite simple, but I am having a hard time to prove it rigorously.

Consider $n\in\mathbb{N}$ vertices, for example $\{v_1,\ldots, v_n\}$. I have some further information on these vertices, namely, that any of these vertices has at least one connection (by an edge) to itself or to any other of the vertices.

Now I would like to prove, that there must be a subset of $\{v_1,\ldots, v_n\}$, which form a connected graph. Even the subgroup $\{v_1,\ldots, v_n\}$ would be allowed.

One more information to consider: I call a subset of $\{v_1,\ldots, v_n\}$, which contains only one element, connected, if it is connected to itself by an edge.

In the best case, I would like to prove this through a contradiction: "Suppose, all subsets do not form a connected graph." However, I cannot find the contradictory statement, that follows from this false assumption.

Again, the statement itself seems very obvious, but I would like to prove it rigorously.

Any help is appreciated! Thank you in advance!

Answer 1

Either I am missing something or the Question is missing something.

Let $V=\{a,b,c,u,v,w,x,y,z\}$ & Edges are $\{ab,bc,uu,uv,vw,ww,wx,wy,xy,zz\}$ where each Vertex is connected to something, maybe itself.

In set $V$, take some "Starting Element", Eg $u$, into new set $U=\{u\}$.
It is given that $u$ is connected to something (maybe itself), then take all other elements which are connected to $u$ (that is $u,v$) & include these in $U$ to get $U=\{u,v\}$.
Then take all elements connected to new element $v$ (that is $w$) & include in $U=\{u,v,w\}$. Again take all new elements in $U$ (that is $w$), & include all connected elements (that is $w,x,y$) then $U=\{u,v,w,x,y\}$.
Again, include all elements which are connected to these new elements (that is $x,y$) where we get no new elements, hence we terminate our algorithm and say that $U=\{u,v,w,x,y\}$ is Maximally Connected.

Maximally Connected means : Including $a,b,c,z$ will make it unconnected.

We will get same $U$ when "Starting Element" is some other element of this $U$.
With "Starting Element" $a$, we will get $U=\{a,b,c\}$
With "Starting Element" $z$, we will get $U=\{z\}$

It seems very straight forward, hence Doubting whether I missed something !

In case we want $|U|$ to be Maximum, then we should try out all "Starting Elements" in the unconnected elements of $V$ & keep track of the Maximally Connected $U$ with Maximum Number of Elements.

Answer 2

A graph $G:=(E,V)$ is connected if there exists a path from any node to any other node in the graph.

The main property $P$of the graph $G$ you are looking at is that every vertex is associated with at least one edge, possibly to itself. Specifically,

$$P\equiv\forall v \in V\; \exists e_{ij} \in E: i=v \text{ or } j=v$$

You also state that a single node with an edge to itself counts as connected, which is consistent with the definition of a connected graph.

Your conjecture $C$ is that there is at least one connected subgraph in $G$:

$$C \equiv \exists V_H\subset V: G_H:=(E_H,V_H)\;\;\text{ is connected}$$

I'll consider two cases.

Case 1: Trivial Case

If $\exists v \in V: e_{vv} \in E$ then $G_H=(\{v\},\{e_{vv}\})$ is a connected subset; therefore, $C$ is true.

Case 2: No loops

If there are no self loops, then every node is connected to one other node. Therefore,

$\exists v,w \in V: e_{vw} \in E \implies G_H=(\{v,w\},\{e_{vw}\})$ is a connected subgraph.

Therefore, $C$ is true $\square$.