4
votes
2answers
72 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
0
votes
2answers
61 views

Undirected Graph Bipartite

I am unsure how to approach this problem: Prove that an undirected graph is bipartite if and only if there are no edges between nodes at the same level in its BFS tree. (An undirected graph is ...
2
votes
2answers
169 views

Proving and Modeling Logical Consistence

Suppose I have a finite list of logical statements (would these be called axioms?) and for the sake of discussion say that there are 6 such statements. All statements are in the form of propositional ...
3
votes
0answers
306 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...