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
7 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
1
vote
1answer
12 views

Number of Labels used in reduction of Isomorphism of Labelled Graph to Graph Isomorphism

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the ...
4
votes
0answers
31 views

2-connected graph problem (West, Introduction to Graph Theory, ex. 4.2.15)

I am struggling with this problem for hours but it seems to be easy. Here is the problem: Proof that every vertex $v$ in 2-connected graph $G$ has neighbour $u$ such that $G - v - u$ is connected. ...
1
vote
0answers
21 views

references of discrete association scheme

I tried to find a book or paper to understanding discrete association scheme but I could not get any book for that. What is the good references for that?
1
vote
1answer
18 views

Graph nomenclature for class-grouped vertices and edges

Is there a name for the subset of graph theory dealing with vertices and edges of distinct classes? For example, I could have a graph in which each vertex must be either blue, yellow or red and each ...
2
votes
1answer
32 views

Prove this simple graph is not planar.

Graph I need to show this graph is not planar. I've attempted to find $K_5$ and $K_{3,3}$ as a subgraphs but haven't been successful yet. It's possible but unlikely this graph is planar but I haven't ...
1
vote
2answers
28 views

Connecting up boxes mathematically (Puzzle)

How would you connect each black box once to each colored box without any lines overlapping, this is racking my brain so please help. Note that you can move the boxes where ever you want. Maybe ...
0
votes
1answer
14 views

How many mappings are there between these two graphs?

Let $P_{20}$ be a path of length 20 like so: $x_0$-$x_1$-$~\cdots~$-$x_{20}$ and $G$ a cycle of order 3. Allegedly there are $3 \cdot 2^{20}$ mappings $P_{20}\rightarrow G$, which I don't quite see. ...
1
vote
1answer
48 views

What kinds of transformations preserve network topology?

I have been reading a number of "network science" papers where the authors perform transformations on networks that seem to preserve the topology of those networks. By "topology", I mean a collection ...
0
votes
1answer
22 views

graphs with smallest eigenvalue at least -1

Let $G$ be an undirected simple graph and let $A$ be its adjacency matrix. It is easy to see that $A$ is neither positive semidefinite nor negative semidefinite. I would like to know if there are ...
1
vote
0answers
42 views

Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases?

In software engineering, there is a coverage metric for testing called modified condition/decision coverage, or MC/DC for short. This metric is well-known in the avionics industry due to showing up in ...
1
vote
0answers
22 views

Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
2
votes
2answers
35 views

Unsolved problems in graph theory

Is there a good database of unsolved problems in graph theory?
3
votes
1answer
33 views

Colored graph isomorphism reduction to uncolored graph isomorphism

I am trying to find a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism. Doing a search on this problem, I found this article and it seems like theorem 1 is ...
0
votes
1answer
11 views

Graph Theory Proof Degree Question

Let G be a graph of order n. Prove that if deg u + deg v ≥ n - 2 for every pair u, v of nonadjacent vertices of G, then G has at most two components.
0
votes
0answers
15 views

Degrees of vertices in a circuit must be even

Let $G$ be a graph with a circuit. Let $C$ denote the subgraph of $G$ consisting of vertices and edges of the circuit. Then for every vertex in $C$, $\deg (v)$ considered in $C$ is even. I would ...
0
votes
2answers
12 views

Removing an edge from a circuit on a connected graph

Let $G = (V,E)$ be a connected graph. Suppose $e$ is an edge in a circuit of $G$. Show that the new graph $(V,E-\{e\})$ is still connected. Attempt: Let $v,w \in V$ be vertices. Then inside $G$, ...
1
vote
1answer
28 views

show that the maximum degree of the graph is 6

Let p1, p2, . . . , pn be n points in the plane such that the distance between any two points is at least one. Let G = (V, E) be the graph such that V = {p1, p2, . . . , pn} and E = {pipj | distance ...
0
votes
0answers
19 views

Does K_4 with an edge removed contain two or three cycles?

I need to answer a question about Cycle Hitting Sets. Such a set if a set that contains at least one edge from every cycles of the graph. My question is. Say we have two adjacent faces. Are there ...
0
votes
1answer
12 views

Calculating the probability of a graph being Erdos-Renyi

Given an undirected, unweighted graph with |V| = 11 and |E|= 19 and given probability p=0.5 I have to calculate the probability of the graph being generated using the Erdos-Renyi Model. I applied the ...
1
vote
1answer
57 views

The set of isomorphisms from a right coset of the automorphism group $Aut(X)$ in $S_n$.

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , on page 22- Theorem 4 Let $X$ and $X'$ be two isomorphic graphs with vertex set $V = \{1 ..... n\}$ , Then the set of ...
0
votes
1answer
11 views

Given an undirected connected simple graph with distinct edge weights.

Given an undirected connected simple graph with distinct edge weights. If we add a constant value to each edge of graph then : single source shortest path of new graph can be changed? My attempt : ...
1
vote
0answers
20 views

Bipartite graphs whose minimal cycles have length $4$

Is there some literature about bipartite graphs whose minimal cycles all have length $4$? By that I mean that any cycle in the graph with length strictly greater than four can be divided into cycles ...
0
votes
0answers
20 views

edge probability graph

I apologize if this is something very trivial, but I couldn't find an answer to it anywhere: I have a directed graph with n = 280 nodes and ...
0
votes
0answers
16 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
-1
votes
1answer
36 views

an edge coloring of $k_{16}$ with no monochromatic triangle [on hold]

My plan is to show that $R(3,3,3)$ is more than 16. So, i want to prove it with graph-theory. i know i should find an edge coloring of $k_{16}$ which contains no monochromatic triangles. Can anyone ...
0
votes
0answers
13 views

Upper bound on the product of independence number and transversal for graph

I am trying to prove if $G$ is an $n$ vertex graph such that $|E(G)| \leq \alpha(G)\tau(G)$, then $|E(G)| \leq \frac{n^2}{4}$ where $\tau(G)$ is the smallest transversal in $G$. A transversal is a ...
0
votes
0answers
22 views

What is a Hungarian forest: definition

I have a doubt in the definition of the Hungarian forest. This is from the book Matching theory by Lovasz. Let $G$ be a bipartite graph with partite sets $A,B$ and let $M$ be a matching of $G$. Let ...
0
votes
0answers
10 views

Deleting vertex v from tree T leaves degree(v) components.

I don't really know how to approach this apart from: delete vertex v entails that you've deleted degree(v) edges, when you delete an edge form a tree you are left with exactly two components, .... ...
0
votes
2answers
38 views

smallest Bipartite Graph

Definition: A graph G is bipartite if its vertices can be partitioned into two sets V1 and V2 and every edge joins a vertex in V1 with a vertex in V2. Bipartite graphs can be characterized by all ...
0
votes
2answers
14 views

Each regional of a maximal planar graph is a triangle

Show that every region of a maximal planar graph is a triangle. A planar graph G is called maximal planar if the addition of any edge to G creates a nonplanar graph. Will this proof use the ...
3
votes
1answer
42 views

Prove that a one-color $K_4$ exists in a two-color $K_{18}$

An edge coloring of a graph is an assignment of colors to the edges of the graph. I have $K_{18}$ colored with blue and red and I want to show that it contains a $K_4$ colored with just one color. ...
0
votes
2answers
42 views

Can someone give a quick explanation of what this exercise wants from me?

I am having trouble understanding exercise 1.25 from the picture below. I know what order means, but the second sentence puzzles me. I have included the exercises before it in the case that 1.25 ...
1
vote
1answer
22 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
1
vote
0answers
33 views

Graphs of (un)bounded color valence

Talking about colored graphs there is a definition given for graphs with bounded color valence. This definition is as follows: A vertex-colored graph $G=(V,E)$ has bounded color valence, if there ...
0
votes
0answers
55 views
+50

How to number the left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$. Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed ...
0
votes
1answer
22 views

Solve logistic problem with graph - fitting boxes

Suppose you have $n$ boxes, each of which falls into one of the $k$ sizes, and you want to nest smaller ones into larger ones, such that no two boxes $A$ and $B$ are nested inside the same box, if ...
0
votes
1answer
19 views

prove that k-cube has $2^k$ vertices, $k$ $2^k$ $^-$ $^1$ edges and is bipartite.

The k-cube is the graph whose vertices are the ordered k-tuples of 0's and 1's, two vertices being joined if and only if they differ in exactly one coordinate. Show that the k-cube has $2^k$ vertices, ...
0
votes
1answer
35 views

Translate this problem to graph theory

Say I have a size $k$ set called $S_k$ with elements that are natural numbers (repetitions are allowed). For instance $\{2, 8, 6, 6, 1, 3\}$ is a valid set for $k = 6.$ I am trying to find the least ...
1
vote
1answer
8 views

Size of minimum vertex cover on complete graph

I know that the maximum size of an independent vertex set, also known as the independence number and denoted by $\alpha$, plus the the size of the minimum vertex cover, $\tau$, is equal to the number ...
-1
votes
0answers
35 views

In graph theory, what would a negative number of vertices mean? [closed]

I'm interested in expanding the concept of vertices into negative numbers. What properties would they have? I'm thinking perhaps extending V - E + F = 2 to begin.
0
votes
1answer
23 views

Let $G=(V,E)$ be the Rado Graph. Suppose $V_1 \cup V_2=V$. Show that one of the induced subgraphs of $G$ on $V_1$, $V_2$ is also Rado.

I started off with: one of $V_1$ or $V_2$ must be countably infinite. WLOG (without loss of generality) Let $V_1$ be countably infinite. I am not sure how to proceed after this.
0
votes
1answer
14 views

How to prove that adjacency matrix is L.I. if a graph contains no cycles?

Consider the vector space $F_n^2$ , and, as usual, let $e_i$ denote the vector with 1 at the $i$th coordinate, and 0 at all others. Call a vector of the type $e_i + e_j$ an edge vector, (think ...
0
votes
0answers
30 views

What is a “box” in this context “let $B ⊂ R^n$ be a box that can be partitioned into boxes”? [closed]

Let $B ⊂ R^n$ be a box which can be partitioned into a finite number of boxes, each of which possesses a direction in which its length is an integer. Show that $B$ also has an integer length ...
2
votes
1answer
36 views

finding edges of a triangle graph from degrees of points

my theory: Given a list of points on a 2 dimensional plane, and the degree of each point, there should correspond only one way to arrange the edges between points so that the final graph is a mesh of ...
0
votes
2answers
44 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
2
votes
3answers
125 views

How Graph Isomorphism is used to determine Graph Automorphism?

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage- For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes ...
0
votes
0answers
12 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
-2
votes
0answers
20 views

Sending flow through a graph so that flow through each node is at most $f$

Given a graph $G$ with source $s$ and sink $t$, suppose we want to send $f$ units of flow from $s$ to $t$ such that at most $p$ units of flow are sent through each node. The edges have infinite ...
6
votes
3answers
159 views

Is there any algorithm to find Isomorphism function between two graphs?

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a ...