Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
0answers
88 views

sum of chromatic numbers

How I can prove that in given simple graph G in n vertices: $$\chi(G) + \chi(\overline{G}) \leq n + 1.$$ Where $\chi$ is chromatic number. I tried to do like that: $$\chi(G) \leq \Delta(G) + 1 \;; ...
0
votes
1answer
52 views

search algorithm BFS?

So i have a recursive search algorithm here, ...
0
votes
0answers
47 views

question about omitting two petersen graph from $K_{10}$ .

prove that if we omit two petersen graph which has no common edges from $K_{10}$ we will get a cycle with 10 vertices which every two vertices which are in front of each other will be adjacent. ...
3
votes
0answers
84 views

Prove that the property of being bipartite for a graph is recognizable.

Prove that the property of being bipartite for a graph is recognizable. Definition: A graphical parameter or graphical property is recognizable if for each graph $G$ of order at elast 3, it's ...
0
votes
1answer
39 views

Find all solution to the deck of following card

Find all solution to the deck of following card there is 7 cards, so I know that the graph $G$ has order $n=7$. Let $m_i$ be the size of $G-v_i$ for $1 \leq i \leq 7$ then $$m=\frac{\sum_{i=1}^n ...
1
vote
0answers
70 views

Prove that if $G$ is reconstructible, then $\overline G$ is reconstructible.

a) Prove that if $G$ is reconstructible, then $\overline G$ is reconstructible. b)Prove that every graph of order $n≥3$ whose complement is disconnected is reconstructible. For a), the book tell me ...
1
vote
1answer
22 views

For a given finite group $Г$ , determine an infinite number of mutally nonisomorphic graphs whose groups are isomorphic to $Г$.

For a given finite group $Г$ , determine an infinite number of mutally nonisomorphic graphs whose groups are isomorphic to $Г$. I know that $Г$ is generated by $\Delta$ and for any finite $Г$, there ...
1
vote
1answer
66 views

Proof that a bipartite graph cannt exist with this degree sequence

Is there a bipartite graph with degree sequence $3,3,3,3,3,6,6,6,6,6,6,9$? Answer is No.Here's my justification: Suppose there exists such a bipartite graph G with the given degree sequence.And ...
3
votes
0answers
208 views

Upper bound for the sum of chromatic number of a graph and chromatic number of its complement

I need to prove that for any simple graph $G$ on $n$ vertices the following inequality is true: $\chi(G)+\chi(\overline {G}))\le n+1$; where $G$ is a simple graph, $\overline{G}$ its complement, ...
3
votes
1answer
43 views

Infinite graphs satisfying a certain Ramsey property

Let $G$ be a countably infinite graph. If $G$ has cliques of arbitrarily large finite size, then $G$ satisfies the following property, which I will call $(*)$: for any $r\in \mathbb{N}$ and any ...
3
votes
5answers
156 views

How do I succinctly note the sum of $(n-1)+(n-2)+…$?

I was playing with numbers and wanted to see how many possible connections there are in a network of $n$ nodes. I found that the answer was equal to ...
0
votes
1answer
83 views

Expressing a hypercube subset definition using set notation

The definition of a hypercube is this: The $n $-dimensional hypercube $Q_n$ is the graph with $V = \left\{{ (e_1,\dots,e_n)|e_i \in \left\{{0,1}\right\}(i=1,\dots,n)}\right\}$ in which two ...
0
votes
1answer
67 views

Graph Theory. Induction Hypothesis.

I would like prove that: A graph contains an Eulerian cycle if and only if the graph is connected and every vertex has even degree. I'm going to try this by induction. How I can formulate the ...
1
vote
1answer
85 views

What would a Steiner tree look like for the vertices of a heptagon?

As it happens, I am currently frantically writing loads and loads of words for NaNoWriMo. One of the chapters I will be writing tonight essentially has the characters approximate a Steiner tree on ...
3
votes
1answer
678 views

Show that Peterson Graph has no 7 cycle

In order to prove that Peterson graph has no 7 cycle I read the proof given in http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf The given proof is ...
3
votes
0answers
119 views

existence of a spanning subgraph with min degree $\delta$ and at most $(n-1)\delta$ edges

Question: G is a graph with n$\ge$2 vertices an min degree $\delta$. Prove that G contains a spanning sub graph of a min degree $\delta$ with at most $(n-1)\delta$ edges. Thoughts: For the induction ...
1
vote
1answer
86 views

on the color classes of a $k$ chromatic graph

Let $G$ be a graph wich is $k$-chromatic. Suppose we have a coloring $(V_1, \ldots, V_l)$ such that each $V_i$ contains at least $2$ elements. I want to prove that $G$ has a $k$-coloring with this ...
0
votes
1answer
42 views

How many possible 2-colorings of a disconnected bigraph?

Is there a relationship between the number of connected components in a bigraph and the number of possible 2-colorings? A connected bigraph (i.e. only one component) can be 2-colored in exactly two ...
0
votes
1answer
52 views

Proof for k-connectedness of random graphs

I am really new to the theory of random graphs. It seems a lot of articles take for granted that: For $k\in\mathbb{N}\setminus\{0\}$ and $p\in(0,1)$ fixed, almost every graph in $G(n,p)$ is ...
1
vote
1answer
101 views

Number of $q$-colorings of an $n\times n$ grid graph without adjacencies

Suppose a square grid graph $g$ of side length $n$ can be colored with $q$ colors. In how many unique colorizations are no adjacent vertices the same color? A friend and I have been trying to find a ...
3
votes
5answers
299 views

Halting probability of random tree-generating algorithm

Suppose I have a tree-generating algorithm as follows. Begin with one root vertex. With equal probability, create either three subvertices or none. Recurse and repeat for each of the subvertices (if ...
0
votes
2answers
243 views

games in a round-robin tournament

How many games are played in a round-robin tournament held with n tennis players where each of the players will play against every other player exactly once. The answer is $\frac{n(n-1)}{2}$. What ...
0
votes
1answer
490 views

Bipartite Graph and Non-connected node?

Is this one bipartite graph or not? It is a simple question for you but i can't find the answer.
2
votes
1answer
117 views

Checking two graphs to be homeomorphic

How can I check that two simple connected graphs are homeomorphic? I know the defenition of homeomorfism, but I can't figure out when to stop subdividing, algoritmically. I need here some stopping ...
1
vote
1answer
16 views

Name for “Stratified” or “Synchronized” directed acyclic graph?

This may be a stupid question, but is there a name for a directed acyclic graph in which: every node can be organized into separate, sequential "bins" any two adjacent "bins" of nodes are a (not ...
0
votes
2answers
43 views

Proof. Theory graph. Please check.

If graph $G = (V,E) $ where $|V| = n $ is connectivity then $ n-1 \le |E| $ My proof: The our thesis is: $ \forall G $ is connectivity $\Rightarrow$ $ n-1 \le |E| $ I prove that using 'reductio ...
0
votes
1answer
524 views

Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

Let G be a simple graph with 25 vertices and 6 connected components. Find (i) the minimum number of edges that G can have. (ii) the maximum number of edges that G can have. What I know: The maximum ...
0
votes
1answer
67 views

prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6

Question: prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6. My proof: By induction. For n=7, the number of edges is 21=$2 ...
0
votes
2answers
24 views

Connecitivity graph. Easy task.

Let $G=(V,E) $ is a connectivity graph and $e\in E$ . Prove that $G'=(V, E - \{e\} ) $ is connectivity $\iff$ e is an edge $\in$ any cycle in $G$. Please help me with that.
0
votes
1answer
27 views

Why $f^{+}(v)-f^-(v) =val(f)$ if $v$ is the source?

I'm reading Bondy/Murthy's Graph Theory: He defines $x$ as the source and $y$ as the sink, reading a bit later in the chapter, he presents this definitions: $$ f^{+}(v)-f^-(v) = \left\{ ...
0
votes
2answers
43 views

Counting non-isomorphic graph.

How many exists non-isomorphic 4-regular graphs $G = (V,E)$ where $|V|=7$ vertices? I'm asking for hint to solve it with group theory( if it is possible) and without them
1
vote
1answer
44 views

Number of spanning trees for this graph

Find $\tau(G)$ for the graph $G$ below. This is what I tried so far: Let $e$ denote the horizontal edge between the two vertices as shown below. I wanted to use $\tau(G) = \tau(G-e) + \tau(G \circ ...
2
votes
2answers
101 views

Number of length-n paths in a graph with a fixed start vertex

So I was looking at a few past-years' papers from the ZIO (an IOI qualifier held here in India), and I found this question: I think this is the same as finding the number of paths of (let's take (a)) ...
3
votes
2answers
103 views

Proving a graph with $11$ vertices and $53$ edges is Hamiltonian

I have a graph with $11$ vertices and $53$ edges and I'm trying to prove it is Hamiltonian. I know that a graph is Hamiltonian if $n \geq 3$ and $d(v) \geq \frac{n}{2}$. I'm just having trouble ...
-2
votes
1answer
154 views

Alternatively eliminating vertexes from graph

Anna and John play on a graph G, alternatively selecting distinct vertexes from it such that for each i > 0, v[i] is adjacent to v[i−1]. Loses the one who can't select anymore a vertex. Prove that if ...
-2
votes
1answer
427 views

Perfect matching of a tree

I wanted to prove that a tree $T$ has a perfect matching if and only if $T-v$ $(v \in V)$ has exactly one odd component for all $v$ which are vertices of the graph. (An odd component is a component ...
-1
votes
1answer
45 views

Graph theory intro

For every graph G, prove that (vertex cover of G) is less than or equal to (twice it's matching). I tried a couple of examples and it works but I can't follow a trend to build my proof. Does anybody ...
1
vote
1answer
139 views

Partitioning a planar graph into spanning trees?

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions ...
1
vote
1answer
32 views

Describe the automorphism group of the digraphs

Describe the automorphism group of the digraphs Here is what I got so far For $D_1$, because of the direction of $vw$, we can't do anything to the graph so $Aut(D_1)= I$ For $D_2$, we can flip the ...
4
votes
1answer
29 views

Proving an equality in degree function in an undirected graph

Given an undirected graph $G=(V,E)$, and a permutation $\pi$ of the vertices, denote by $\Delta_\pi$ the $\max_{1\leq i\leq n-1} \{\deg_{\{v_{i+1},...,v_n\}}(v_i)\}$. That is, we look only on the ...
3
votes
1answer
70 views

NP completeness path problem.

We have the following decision problem. Let $G=(V,E)$ be a directed graph with edge weights $w:E \to \mathbb{R}_{+}$ and $B \in \mathbb{R}$. Is there a set $K$ consisting of directed vertex-disjoint ...
2
votes
1answer
27 views

Determine the number of distinct labeling of $K_{r,r}$

Determine the number of distinct labeling of $K_{r,r}$ In $G=K_{r,r}$, every vertices has degree $r$ so $|Aut(G)|=r$. I also know that the number of distinct labeling of $G$ of order $n$ is $\frac ...
3
votes
2answers
86 views

Why this graph has automorphism group is isomorphic to the cyclic group of order 4?

My professor say that this graph is a non-separable graph whose automorphism group is isomorphic to the cyclic group of order 4 without telling me why I can see this graph has no cut vertex, so ...
1
vote
1answer
275 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
1
vote
0answers
37 views

are graphs/networks additive

I was wondering if networks/graphs are the sum of their parts. Let's say you have a 15-node network. The spectral density of that network has X kurtosis and Y skewness. You also have a 20-node ...
0
votes
1answer
58 views

Graph Theory into

Let $M$ and $N$ be matchings in a graph $G$ with $\lvert M\rvert > \lvert N\rvert$. Prove that there exists matchings $M'$ and $N'$ such that $\lvert M'\rvert = \lvert M\rvert-1$, and $\lvert ...
3
votes
1answer
53 views

Graph theory proofs

I am trying to prove that half of the vertex cover of graph is less than it's matching number. The problem is I don't know how to start and what the solution should be like, please help!
2
votes
1answer
230 views

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
1
vote
0answers
87 views

Random Spanning Tree Edge Probability

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees from a graph. The problem has many parts, but there are two hints to help with the more complicated ...
0
votes
1answer
33 views

Measure for presence of several poorly interconnected components in undirected graph

Is there a measure to classify networks regarding whether or not they are composed of several (internally closely connected) groups which are poorly connected (i.e. few links between groups). That ...