1
$\begingroup$

Definition

A connected component of an undirected graph $G$ is a subgraph where any two vertices are connected by paths. A connected component is a maximal connected subgraph in $G$.

Consider a complete graph $K_3$ and its subgraphs. I cannot understand the word maximal so I get the following question that I want to get confirmed by the subquestions to be totally certain about the term connected component.

enter image description here

Is a connected component unique?

  1. Is the connected component the triangle graph for all different subgraphs of $K_3$ (yes)?

  2. Does there exist other connected components for some subgraphs of $K_3$?

    2.1. Are the V-shaped graphs the connected components of the triangle graph at the top (a path exists to connect all vertices)?

    2.2. Or is the only connected component the maximal subgraph, the triangle graph here?

  3. What does the word maximal really mean here? Not required to be unique (so not using the term maximum connected component)? The triangle graph is the maximum connected component of all subgraphs of $K_3$?

$\endgroup$
  • 5
    $\begingroup$ Maximal as in inclusion; that is, no other connected subgraph of $G$ contains that connected component. $\endgroup$ – Fimpellizieri Jun 17 '16 at 3:03
  • $\begingroup$ @Fimpellizieri I understand that maximal infers "not necessarily unique" but I understand your comment "no other connected subgraph of $G$ contains that [cc]" to mean "maximum connected component": can you clarify why it is called maximal cc instead of maximum cc? $\endgroup$ – hhh Jun 17 '16 at 23:10
  • $\begingroup$ Maximum refers to a greatest element. Maximal refers to an element that is not smaller than any other element. For total orders (think real numbers), these are the same, but not for partial orders (like inclusion). There can only ever be at most one maximum element, but there may be multiple maximal elements. Zorn's Lemma, for instance, is about finding a maximal element when handpicking one might be difficult. For more info/examples on maximum vs maximal elements, see this wikipedia link. $\endgroup$ – Fimpellizieri Jun 18 '16 at 2:22
2
$\begingroup$

Your "Definition" underlaid in khaki is slightly lopsided.

Given an undirected graph $G=(V,E)$ call two vertices $x$, $y\in V$ equivalent if there is an edge path connecting $x$ and $y$ in the obvious way. Each equivalence class $C_\iota\subset V$ together with the edges connecting the $x$, $y\in C_\iota$ is called a connected components of $G$. If there is just one such component, i.e., if any two vertices $x$, $y\in V$ can be connected by an edge path in $G$, then the graph $G$ is called connected.

Given a graph $G$ there are many subgraphs $G'$ of $G$, some connected, some consisting of several connected components. It is easy to see that a connected component $C=(V',E')$ of $G$, in the sense defined in the first paragraph, is a maximal connected subgraph of $G$, since there is no vertex $z\in V\setminus V'$ that is connected to a single vertex in $V'$, let alone to all of them.

$\endgroup$
  • $\begingroup$ So equivalance classes form vertex set partitioning, I like this definition +1 but why is this called "maximal connected subgraph" instead of "maximum connected subgraph". Because the cc of a graph is unique as by graph-inclusion, I cannot understand the terminology to call it maximal instead of maximum, can you please clarify that, thank you! $\endgroup$ – hhh Jun 17 '16 at 23:13
  • $\begingroup$ And on "edge path", do you mean an alternating sequence of vertices and edges without repetition of vertices in the sequence? (I have learnt this to mean just path so curious whether "edge path" is this?) $\endgroup$ – hhh Jun 17 '16 at 23:54
  • 1
    $\begingroup$ I agree that the definition of connected component in the question is not correct enough. The definition in this answer is correct. Again connected components are not maximum. See the example in answer. That graph has two connected components. Also the bottom graph in your question has 3 connected components as all 3 vertices are not connected to any other vertices. $\endgroup$ – Mosquite Jun 20 '16 at 16:43
0
$\begingroup$

Yes, for a given graph, the connected components are uniquely defined (there can be several CC per graph).

The definition is given in terms of connected subgraphs, i.e. subgraphs "made of a single piece". A connected subgraph is maximal, hence is a connected component, if you can't make it larger, i.e. if no other vertex is connected to it.

Consequently, every connected subgraph is included in a single connected component.


Q1 and Q2: Among the $5$ graphs, the three on the top have a single CC, the middle one has two and the third one three. (An isolated vertex is a CC.)

Q3. In the top graph, a subgraph made of two vertices isn't maximal as it is connected to the third vertex.

$\endgroup$
  • $\begingroup$ On "a subgraph made of two vertices isn't maximal as it is connected to the third vertex." -- did you mean "In the top $\triangle$ graph, a subgraph $H$ with a path graph $\cdot-\cdot$ and an isolated vertex $h$ isn't maximal as the path graph is NOT connected to $h$ by any edge path"? Because $H\not\subset\triangle$, $\triangle$ is not a CC of $H$? So $\triangle$ is not a maximum cc but the triangle graph $\triangle$ is maximum within $K_3$ by graph-inclusion? (not by cc criteria) $\endgroup$ – hhh Jun 17 '16 at 23:28
  • 1
    $\begingroup$ On the top graph, a subgraph with only two vertices and one edge isn't maximal as there exist connections to the third vertex. $\endgroup$ – Yves Daoust Jun 18 '16 at 7:42
0
$\begingroup$

A connected component is not necessarily unique. In the graph, $H$, below:

enter image description here

we have two connected components $G_1$ and $G_2$.

However, most of the graphs you will encounter in a graph theory course are connected and thus only have 1 unique connected component.

Now to answer your question.

1 and 2. The first graph has the triangle graph as its connected component. The second level graphs have the V graph as their connected component. The third level graph has two connected components: a single vertex and a the two vertices connected by an edge. The fourth level graph has three connected components each a single vertex.

  1. A connected component, $G$ is maximal in the sense that there are no other subgraphs that contain $G$ and are connected. (As per @Fimpellizieri)
$\endgroup$
  • $\begingroup$ I think we understand the point 2.2 differently: the triangle graph $\triangle$ is not a CC of the graphs such as the isolated vertices or V-shaped graphs, right? So $\triangle$ is not maximal cc of other graphs in $K_3$, it is only the maximal cc of $\triangle$ itself. It is true that $\triangle$ is the maximal, also maximum graph in $K_3$, by subgraph inclusion (all subsgraphs are subsets of it) but it does not mean that $\triangle$ is a CC of other subgraphs in $K_3$, agree? $\endgroup$ – hhh Jun 17 '16 at 23:35
  • $\begingroup$ The triangle graph is not a connected component of the other graphs because it is not a subgraph of those graphs. A connected component is maximal in the sense that adding any positive number of edges and vertices from the original graph will not result in a connected graph. $\endgroup$ – Mosquite Jun 20 '16 at 16:48
  • $\begingroup$ I see that I misread your first question. I edited my answer to address this. $\endgroup$ – Mosquite Jun 20 '16 at 16:54

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.