## 2 Formal Definition and Properties
In \(G\), there is no proper subgraph of \(G_{s}\) satisfying (1) and (2) (smallest one property). Given a vertex \(q\) in \(G\), we are interested in the SUIS of graph \(G\) containing position \(q\), denoted as SUIS(\(q\)), which is closely related to MUIS. Figure 3 shows an example of SUIS and SUIS(\(q\)). Assume \(q=v_{5}\), \(G_{s1}\) is not an SUIS of \(G\), but it is an SUIS(\(q\)). Below is the verifying process:  
First, it is easy to verify that \(G_{s1}\) is an induced subgraph of \(G\) according to Definition 3. Second, we can verify that \(G_{s1}\) is unique according to Definition 4. Third, on the one hand, since \(\{\{v_{1},v_{2}\},\{v_{(1},v_{2})\}\}\), an induced subgraph of \(G_{s1}\) is also unique, and \(G_{s1}\) is not an SUIS. On the other hand, all the induced subgraphs of \(G_{s1}\) containing \(q\), except itself, \(\{\{v_{5}\},\emptyset\}\), \(\{\{v_{1},v_{5}\},\{v_{(1},v_{5})\}\}\) and \(\{\{v_{2},v_{5}\},\{v_{(2},v_{5})\}\}\), are not unique. \(G_{s1}\) satisfies the smallest one property when taking into account \(q\), so \(G_{s1}\) is an SUIS(\(q\)). \(G_{s2}\) is both an SUIS and an SUIS(\(q\)) of \(G\), which can also be verified by the same method. The example clearly shows the difference between SUIS and SUIS(\(q\)). **Definition 8**. : _(MUIS) For a graph \(G=(V,E,l)\) and a vertex \(q(\in V)\), the MUIS subgraph is the induced subgraph in the set of SUIS(\(q\)) of \(G\) with the minimal number of vertices, denoted as MUIS(\(q\)). More intuitively, MUIS(\(q\)) is the induced subgraph of \(G\) containing \(q\) with the minimal number of vertices, which is unique._  
Vertex \(q\) is called the query vertex or query position. Obviously, MUIS is a concept that is closely related to the query position. Similar to SUIS, MUIS has the induced subgraph property, uniqueness property and minimality property. For the same graph, a different query vertex may obtain a different MUIS. Figure 3 shows an example of MUIS. Suppose \(v_{5}\) is the query vertex. Both \(G_{s1}\) and \(G_{s2}\) are SUIS(\(q\))s as proven above. The number of vertices of \(G_{s2}\) is more than that of \(G_{s1}\). Since the number of vertices is not minimal, \(G_{s2}\) is not an MUIS. It is easy to find out that the minimal induced subgraph of \(G\) containing the query position is \(\{\{v_{5}\},\emptyset\}\), which is not unique. Furthermore, we can verify that the induced subgraphs of \(G\) containing the query position with two vertices are also not unique. Therefore, \(G_{s1}\) is an MUIS. **Definition 9**. : _(Problem definition) Minimal Unique Induced Subgraph Query (MUISQ) is to find an MUIS for the given graph and query position._  
We show the induced subgraph property, the uniqueness property and the minimality property of MUIS above. Furthermore, we explore the property related to the number of MUISs below. **Number property. ** Given a graph \(G=(V,E,l)\) and a vertex \(q(\in V)\), there exists at least one SUIS, SUIS(\(q\)) and MUIS. Figure 3: An example of the Smallest Unique Induced Subgraph (SUIS) and MUIS. Proof: \(G\) itself is unique. Therefore, at least one SUIS, or \(SUIS(q)\), or MUIS is itself in extreme cases. Therefore, there may exist may induced subgraphs satisfying the conditions. MUISQ is a task to find out any one subgraph satisfying the conditions. There is no need to find out all MUISs.