2 Some basic notions 2.1 Some useful classes of graphs :2.3 Walks, Trails and Paths

2.2 Some basic notions

We shall assume that all our graphs are finite unless mentioned otherwise. In some examples, we shall illustrate things using infinite graphs but all our results are for finite graphs only.

Fix a graph $G$ with vertex set $V$ and edge set $E$ . We say $v, w$ are neighbours if $v\sim w$ .

Definition 2.13 (Graph homomorphism and isomorphism ).

Suppose $G, H$ are two graphs. A function $\phi:V(G)\to V(H)$ is said to be a graph homomorphism if $x\sim y$ implies $\phi(x)\sim\phi(y).$ $\phi$ is said to be an isomorphism if $\phi$ is a bijection and $x\sim y$ iff $\phi(x)\sim\phi(y)$ i.e., $\phi,\phi^{-1}$ are graph homomorphisms. $G$ and $H$ are isomorphic ( $G\cong H$ ) if there exists an isomorphism between $G$ and $H$ . An automorphism is an isomorphism $\phi:G\to G$ .

Exercise(A) 2.14.

The set of all automorphisms of $G$ is called $\operatorname{Aut}(G)$ . Define a binary operation on $\operatorname{Aut}(G)$ as followss : For $g,f\in\operatorname{Aut}(G)$ , $g.f=g\circ f$ i.e., the composition operation. Is $\operatorname{Aut}(G)$ a group ?

Exercise(A) 2.15.

Are the following three graphs isomorphic to Petersen graph ?

Essentially, $G$ and $H$ are the same graphs upto re-labelling. $H$ is a subgraph of $G$ if $V(H)\subset V(G)$ and $E(H)\subset E(G).$ $H$ is an induced subgraph of $G$ if $H$ is a subgraph of $G$ and if $v,w\in H$ such that $(v,w)\in E(G)$ then $(v,w)\in E(H)$ . Alternatively, $H$ is an induced subgraph if $H$ is a subgraph and $E(H)=\binom{V(H)}{2}\cap E(G)$ .

Exercise 2.16.

$H$ is an induced subgraph of $G$ iff $H$ is the maximal (w.r.t. edge inclusion) subgraph in $G$ with vertex set $V(H)$ .

Example 2.17 (Trivial homomorphisms).

The identity automorphism is a trivial homomorphism ; If $H\subset G$ , then the inclusion map from $V(H)$ to $V(G)$ gives rise to a homomorphism.

Lemma 2.18.

Show that there exists a homomorphism from $G$ to $K_{2}$ iff $G$ is bi-partite.

Proof.

If there exists an homomorphism $\phi:G\to K_{2}$ , observe that $V=\phi^{-1}(1)\sqcup\phi^{-1}(2)$ and this defines the correct partition and shows that $G$ is bi-partite. If $G$ is bi-partite with $V=V_{1}\sqcup V_{2}$ then defining $\phi:G\to K_{2}$ as $V_{1}\mapsto 1,V_{2}\mapsto 2$ gives the required homomorphism. ∎

Exercise(A) 2.19.

Define a notion of $k$ -partite graphs and characterize $k$ -partite graphs $G$ using homomorphisms.

Exercise* 2.20.

Denote by $\operatorname{Hom*}(H,G)$ to be the number of injective homomorphisms from $H$ to $G$ . Let $|V(H)|=k$ . Show that

\left|\operatorname{Hom*}(H,G)\right|=\sum^{\neq}_{(v_{1},\ldots,v_{k})\in V(G% )^{k}}\mathbf{1}\big{[}H\subset\left\langle\{v_{1},\ldots,v_{k}\}\right\rangle% \big{]},

where $\sum^{\neq}$ denotes that the sum is over distinct elements and $\left\langle v_{1},\ldots,v_{k}\right\rangle$ is the induced subgraph on the vertices $v_{1},\ldots,v_{k}$ .

See here http://www.cs.elte.hu/~lovasz/problems.pdf for open problems about graph homomorphisms.

Definition 2.21 (Some notions).

Let $\mathcal{G}$ be the set of all finite graphs.

•

Graph property : A set $\mathcal{P}\subset\mathcal{G}$ is said to be a graph property if $G_{1}\in\mathcal{P}$ and $G_{1}\cong G_{2}$ , then $G_{2}\in\mathcal{P}$ .
•

Graph invariant : $\phi:\mathcal{G}\to\mathbb{R}$ is a graph invariant if $\phi(G_{1})=\phi(G_{2})$ whenever $G_{1}\cong G_{2}$ . Equivalently $\phi$ is a graph invariant if $\phi^{-1}(r)$ is a graph property for every $r\in\mathbb{R}$ .
•

Spanning subgraph : $H$ is a spanning subgraph if $V(H)=V(G)$ .
•

Neighbourhood : If $v\in V$ , the neighbourhood of $v$ , $N_{v}:=\{w:w\sim v\}.$
•

Degree : $d_{v}:=|N_{v}|.$
•

$v$ is isolated if $d_{v}=0$ .
•

Regular graph : $G$ is $d$ -regular if $d_{v}=d_{w}=d$ for all $v, w$ .
•

Minimum degree : $\delta(G):=\min\{d_{v}:v\in V\}.$
•

Maximum degree : $\Delta(G):=\max\{d_{v}:v\in V\}.$
•

Average degree : $d(G):=|V|^{-1}\sum_{v}d_{v}.$
•

Edge density : $\epsilon(G):=|E|/|V|.$

Prove that $\delta(G)\leq d(G)\leq\Delta(G).$ This holds true even if $d_{v}$ ’s are negative numbers and can said to be averaging principle . It can be considered to be a basic instance of the more powerful probabilistic method.

Exercise 2.22.

Which of the graphs in Section 3.1 are regular and what are their average degrees ? Can you compute $\operatorname{Aut}(G)$ for these examples ?

Many of the above notions can be generalized to set systems or hypergraphs defined as follows.

Definition 2.23.

(Set systems ) A set system or family of sets ${\mathcal{F}}$ is a collection of subsets of a set $V$ . Set systems are also known as hypergraphs.

Thus graphs are equivalent to set system consisting of $2$ -element sets. Suppose ${\mathcal{F}}=\{A_{1},\ldots,A_{m}\}$ be a set system defined i.e., $A_{1}i\subset V=[n],i=1,\ldots,m$ . The incidence matrix is defined as matrix $M=(m_{i,j})_{1\leq i\leq n,1\leq j\leq m}$ with $m_{i,j}=1[i\in A_{i}]$ . We can define the degree of $v$ in ${\mathcal{F}}$ as $d_{v}({\mathcal{F}})=\sum_{j=1}^{m}m_{i,j}$ . The following two lemmas are a consequence of double-counting argument .

Lemma 2.24.

Let ${\mathcal{F}}=\{A_{1},\ldots,A_{m}\}$ be a set system on $V$ as above. Then

\sum_{v\in V}d_{v}({\mathcal{F}})=\sum_{i=1}^{m}|A_{i}|

The proof is by observing that $d_{v}$ is the row-sum and $|A_{i}|$ is the column-sum in the incidence matrix $M$ . Further specializing to graphs where $A_{i}$ ’s are of cardinality $2$ , we derive the following.

Lemma 2.25.

(Euler 1736) $\sum_{v}d_{v}$ is even. Thus the number of odd-degree vertices is even (handshaking lemma) and $d(G)=2\epsilon(G)$ .

Exercise(A) 2.26.

For a set system ${\mathcal{F}}$ , show that $\sum_{i,j}|A_{i}\cap A_{j}|=\sum_{v}d_{v}({\mathcal{F}})^{2}$ .

Exercise(A) 2.27.

Suppose $G$ is a 3-regular graph on $10$ vertices such that any two non-adjacent vertices have exactly one common neighbour. Is $G$ isomorphic to Petersen graph?

Exercise* 2.28.

What can you say about the minimum degree, maximum degree and average degree of Complementary and Line graphs given those of the original graph?

For a complementary graph,

•

Minimum degree: Pick the vertex $v_{i}$ with the maximum degree in a finite graph $G$ with $n$ many vertices. So $deg(v_{i})\geq deg(w)\forall w\in V(G)\implies n-1-deg(w)\geq n-1-deg(v_{i}).$ Now if $w$ has degree $deg(w_{i})$ in $G$ , then it has $n-1-deg(w)$ in $G^{C}$ . So we get that in $G^{C},v_{i}$ has the least degree, hence

$\delta(G^{C})=n-1-\Delta(G)$
•

Maximum degree: Continuing a similar argument as before,

$\Delta(G^{C})=n-1-\delta(G)$
•

Average degree: As shown, every vertex $w$ in $G^{C}$ has degree $n-1-deg(w)$ in $G^{C}$ where it had degree $deg(w)$ in $G$ . So, for $n$ vertices of $G$ , given as $v_{1},\cdots,v_{n}$ , we have,

$d(G^{C})=\frac{1}{n}\sum_{i=1}^{n}(n-1-deg(v_{i}))=n-1-\frac{1}{n}\sum_{i=1}^{% n}deg(v_{i})=n-1-d(G)$

For a line graph, things get a little complicated.

•

Minimum degree: Suppose a vertex $e_{i}\in V(L(G))$ has the minimum degree $\implies$ $e_{i}$ has the least number of edges it shares a common vertex with in the graph $G$ . Suppose $e_{i}$ connects $v_{p}$ and $v_{q}$ . So basically we should find an edge $e_{i}\in E(G)$ connecting vertices $v_{p}$ and $v_{q}\in V(G)$ such that $deg(v_{p})+deg(v_{q})-2$ is the smallest, or equivalently, $deg(v_{p})+deg(v_{q})$ is the smallest. So basically take

$S:=\{deg(v_{p})+deg(v_{q})|v_{p},v_{q}\in V(G),v_{p}\sim v_{q}\}$

The two vertices whose sum of degrees give the smallest element of $S$ have the edge between them whose degree is the minimum in the line graph. Note: this may not always be the edge connected to the vertex with lowest degree in $G$ .
•

Maximum degree: Similar to the previous argument, the two vertices whose sum of degrees give the largest element of $S$ have the edge between them whose degree is the maximum in the line graph. Note: this may not always be the edge connected to the vertex with largest degree in $G$ .
•

Average degree: Note that $d(G):=|V|^{-1}\sum_{v}d_{v}=2\frac{|E(G)|}{|V(G)|}$ as sum of degrees of a graph is twice the number of edges. So by exercise 2.1.11, we have

$|E(L(G))|=\frac{1}{2}\sum_{i=1}^{n}d_{i}^{2}-m$

where $m=|E(G)|=|V(L(G))|,n=|V(G)|$ and $d_{i}$ is the degree of vertex $v_{i}\in V(G)$ . Hence

$d(L(G))=2\frac{|E(L(G))|}{|V(L(G))|}=\frac{\sum_{i=1}^{n}d_{i}^{2}-2m}{m}=% \frac{1}{|V(L(G))|}\sum_{i=1}^{n}d_{i}^{2}-2$