1
$\begingroup$

Let $G$ be a Petersen graph and $S\subset V(G)$,

how can I compute $e(G[S])$ for non-trivial $S$?

Here $G[S]$ is the induced subgraph of $G$ and $e(G[S])$ is the number of edges of $G[S]$. I think this should be a function of $|S|$, i.e., the size of $|S|$. For specified $S$, say, the five vertices in a 5-cycle, one can come up with $ e(G[S])=|S|=5.\quad[\text{EDITED}] $ But I have no idea how to approach this problem for general $S$.

[EDITED:] Can I bound $e(G[S])$ by a function of $|S|$?

enter image description here

1 Answers 1

2

First of all, I would say that for $S$ being the vertices of a 5-cycle you get $e(G[S])=5$, since in an induced subgraph, you have only the edges between the vertices of $S$.

Moreover, this is not a function in $|S|$. Consider this example of a 5-elementary set $S$. enter image description here

Here you get $e(G[S])=2$.

If you ask how to compute it, then simply test for every edge if its endpoints are both in $S$.