Let $G=(V,E)$ be a finite simple graph. Does there exist a finite set $S$ and $S_G\subseteq P(S)$ such that the intersection graph $H$ of $S_G$ is isomorphic to $G$, i.e. $H\cong G$.

Here's my idea:
If I can find such an intersection graph $H$ that $H\cong G$, then the proposition is proved.
Let $V=\{v_1,\dots,v_n\}$ and $E=\{e_1,\dots,e_m\}$, where $n,m$ are both positive integers since $G$ is finite. Now, let $S=V$, and $S_G=E\cup \{\{v_i\}\}$, where $v_i$ satisfies the condition that $v_i\neq e_j\cap e_k$ for all $j,k\le m$. That is, $v_i$ is a vertex with degree 1. We define the set of edges $F$ by

$$f=\begin{cases} \{v_i,e_i\}&\text{ if }v_i\in S_G\ \text{and}\ v_i\text{ is incident with }e_i\\ \{e_j,e_k\}&\text{ for all }e_j,e_k\in E\text{ with }j\neq k \end{cases}$$

Then $H=(S_G,F)\cong G$.
I find my idea works well for closed graph, but not so well for others. There must be some problems in my idea. Anyone has any idea or can modify my solution?

  • $\begingroup$ What is a "closed graph"? Why is $(S_G,F)\cong G$? What is the isomorphism? $\endgroup$ – bof Dec 6 '17 at 8:34
  • $\begingroup$ By closed, I mean the degree of all the vertices in the graph is at least two. Maybe when I was writing this post, I used the concept of closed walk, or something like that... $\endgroup$ – R.C Dec 6 '17 at 10:36

I don't understand your solution. Here's how I'd do it. Let $G=(V,E)$ be a simple graph, finite or infinite. Let $S=V\cup E.$ (Of course, if $G$ is finite, then $S$ is finite.) For each vertex $v\in V$ let $f(v)=\{v\}\cup\{e\in E:e\text{ is incident with }v\}\in P(S)$ and let $S_G=\{f(v):v\in V\}\subseteq P(S).$ Then $f:V\to S_G$ is bijective and, for distinct vertices $v_1,v_2\in V,$ we have $v_1$ adjacent to $v_2$ if and only $f(v_1)\cap f(v_2)\ne\emptyset.$ That is, $f$ is an isomorphism from the graph $G$ to the intersection graph of $S_G.$

  • $\begingroup$ I understand your method. For my method, I meant to construct a mapping from $V$ to $S_G$ that relates the edges in $E$ to $V\times E$, which was the edges I defined for graph $H$. This is the first case of $f$. In the second case of $f$, I meant to elimate some duplication, but I didn't know exactly how, so I tried some examples and concluded this. $\endgroup$ – R.C Dec 6 '17 at 7:40
  • $\begingroup$ Why are you "defining edges" for the graph $H$? $S_G$ is a collection of sets, and $H$ is its intersection graph, so the adjacencies are automatic: two vertices $x,y\in S_G$ are joined by an edge iff $x\cap y\ne\emptyset$. $\endgroup$ – bof Dec 6 '17 at 8:39
  • $\begingroup$ Okay, I find I misunderstand the concept of intersection graph. And for undirected simple graph, can I write $S=V$ since all the edges in $E$ is unordered pairs, which are in $P(V)$? $\endgroup$ – R.C Dec 6 '17 at 10:32

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.