I am trying to figure out if given a connect graph with N nodes and A edges, its subgraphs are connected.

In order word: given a graph G, can I have a subgraph of G that is not connected? Or: can a subpgraph of G not be connected?

I think the answer is no because otherwise G' is not a (sub)graph.

  • $\begingroup$ Graph theory has a different term for what you think is a subgraph: it's called a component. $\endgroup$ – reinierpost May 2 '19 at 8:59

A subgraph of a graph $G$ is any graph that has a subset of $G$'s vertices and a subset of its edges. In particular, for an graph $G=(V,E)$, the graph $(V,\emptyset)$ is a subgraph that's not connected.

| cite | improve this answer | |
  • $\begingroup$ So are you saying that a graph with only one edge is a subgraph not connected of G? $\endgroup$ – Prova12 May 1 '19 at 21:13
  • $\begingroup$ No, he's saying that if you remove all the edges from a graph, it is a subgraph, and it's not connected. $\endgroup$ – Pål GD May 1 '19 at 21:18
  • $\begingroup$ I'm saying a graph with no edges is a non-connected subgraph of $G$. A graph with exactly one edge is connected if it only has two vertices, and disconnected if it has more than two. $\endgroup$ – David Richerby May 1 '19 at 21:19
  • $\begingroup$ @DavidRicherby the graph $(V,\emptyset)$ is a subgraph that's not connected except when $V$ is a set of a single vertex. $\endgroup$ – John L. May 2 '19 at 1:45
  • 1
    $\begingroup$ @Apass.Jack I can never remember whether people consider the single-vertex graph to be connected so I mostly just ignore it! 😀 $\endgroup$ – David Richerby May 2 '19 at 8:31

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.