6. Special graphs, subgraphs, connectedness

Special graphs

Complete graph

The complete graph on $n$ vertices ($n$-clique), denoted by $\boxed{K_n}$, is the simple graph that contains an edge between each pair of distinct vertices.

Link to original

Draw the graphs of $K_3$, $K_5$, and $K_6$. ?

graph 3 {
	label="K₃"
	layout=circo
	node [shape=point]
	1--2,3
	2--3
}
 
graph 5 {
	label="K₅"
	layout=circo
	node [shape=point]
	1--2,3,4,5
	2--3,4,5
	3--4,5
	4--5
}
 
graph 6 {
	label="K₆"
	layout=circo
	node [shape=point]
	1--2,3,4,5,6
	2--3,4,5,6
	3--4,5,6
	4--5,6
	5--6
}

Complete cycle

The complete cycle(??), $n$-cycle is denoted by $\boxed{C_n}$, for $n \ge 4$.

Link to original

graph 4 {
	label="C₄"
	layout=circo
	node [shape=point]
	1--2
	2--3
	3--4
	4--1
}
 
graph 5 {
	label="C₅"
	layout=circo
	node [shape=point]
	1--2
	2--3
	3--4
	4--5
	5--1
}

Subgraphs

When edges and vertices are removed from a graph, without removing end-points of any remaining edges, a smaller graph is obtained.

Such a graph is called a subgraph of the original graph.

title: Subgraphs of $K_6$
 
```graphviz
graph A {
	layout=circo
	node [shape=point]
	1--3,4,5,6
	2--3,4,5,6
	3--4,5,6
	4--5,6
	5--6
}
 
graph B {
	layout=circo
	node [shape=point]
	1--2,3
	2--3,4
	3--4
}
 
graph B {
	layout=circo
	node [shape=point]
	1--2,3
	2--3
}

Connected graphs

A simple graph is called connected if there is a path between every pair of distinct vertices.

graph G {
	node [shape=point]
	
	subgraph cluster_G {
		label="connected"
		a--b,c,d
		b--c
		d,h--e
		g--h,f
	}
	
	subgraph cluster_H {
		label="not connected"
		1--2,3
		2--3
		4--5
		6--7,8
	}
}

A connected component of a graph is a maximal connected subgraph.

• If a graph is connected, then it has only 1 connected component, itself.

• But if it is not connected, then it can have more:

  graph 1 {
    layout=circo
    node [shape=point]
    a [xlabel="a"]
    b [xlabel="b"]
    c [xlabel="c"]
  	label="G₁"
    a--b,c
    b--c
  }
   
  graph 2 {
    layout=circo
    node [shape=point]
    d [xlabel="d"]
    e [xlabel="e"]
  	label="G₂"
    d--e
  }
   
  graph 3 {
    layout=circo
    node [shape=point]
    g [xlabel="g"]
    h [xlabel="h"]
    f [xlabel="f"]
  	label="G₃"
    g--h,f
  }

  are the three connected components of:

  graph G {
    node [shape=point]
    	
  	subgraph cluster_H {
    	a [xlabel="a"]
    	b [xlabel="b"]
    	c [xlabel="c"]
    	d [xlabel="d"]
    	e [xlabel="e"]
    	f [xlabel="f"]
    	g [xlabel="g"]
    	h [xlabel="h"]
    	label="G₁"
    	a--b,c
    	b--c
    	d--e
    	g--h,f
     }
  }