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
2answers
352 views

Is it true that if a graph is n-regular that it must have n+1 vertices?

In other words if a graph is 3-regular does it need to have 4 vertices? I ask because I have been asked to prove that if $n$ is an odd number and $G$ is an $n$-regular graph that $G$ must have an ...
1
vote
3answers
251 views

Simple connected planar graph with $6$ vertex and $12$ edges , each of the face is bdd

A simple connected planar graph with $6$ vertices and $12$ edges. How do we show that each of the face is bounded by three edges?
1
vote
1answer
4k views

Prove by induction that every connected undirected graph with n vertices has at least n-1 edges

The problem is in the title. Here is the hint given: In the inductive case, try proof by contradiction. For this proof by contradiction, you may need to use the hand-shake lemma and concept of ...
1
vote
1answer
536 views

Unique path between any pair of vertices in $G$

I'm having trouble with this question: Suppose there is a unique path between any pair of vertices in $G$. Prove that $G$ is a tree. I know that a path is a trail where all vertices are distinct ...
1
vote
2answers
255 views

Working out the number of automorphisms of a graph

Take the complete graph with n vertices, where one edge has been removed. How can you work out the number of automorphisms that this graph has?
1
vote
1answer
911 views

Defining a cut-set without referring to partitioning vertices into two groups?

From Wikipedia: a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the ...
1
vote
2answers
479 views

Landau's Theorem on tournaments

There is a Landau's theorem related to tournaments theory. Looks like the sequence $(0, 1, 3, 3, 3)$ satisfies all three conditions from the theorem, but it is not possible for 5 people to play ...
1
vote
2answers
111 views

quick question on showing every edge in a graph of minimum degree n+1 is contained in a hamiltonian circuit.

Show that if every vertex in a graph on $n$ vertices has degree at least $\frac{n+1}{2}$, then every edge $e\in E(G)$ in G is contained in a Hamiltonian circuit. My battle strategy: We know that ...
1
vote
1answer
54 views

Prove the following (graph theory)

Prove that a graph G contains no cycles IF AND ONLY IF the intersection of any two intersecting paths is also a path in G.
1
vote
2answers
387 views

Planar graph proof [duplicate]

Possible Duplicate: How to prove that a simple graph having 11 or more vertices or its complement is not planar? I need to prove some graph problem. Let G be planar graph with more than 10 ...
1
vote
1answer
108 views

Is an abstract simplicial complex a quiver?

Let $\Delta$ be an abstract simplicial complex. Then for $B\in \Delta$ and $A\subseteq B$ we have that $A\in\Delta$. If we define $V$ to be the set of faces of $\Delta$, construct a directed edge from ...
1
vote
1answer
57 views

Graph properties characterized by finitely many 'simplest examples'

Recently I heard someone talking about a general result saying that a graph property satisfying certain conditions always is characterizable via a (finite) set of 'smallest examples' (similar to the ...
1
vote
1answer
863 views

Adjacency list and the adjacency matrix for the directed cycle with 4 vertices and directed wheel with 5 vertices in total

I have encountered a problem while doing exercises in my text book. The question is to write down the Adjacency list and the adjacency matrix for the directed cycle with 4 vertices and directed wheel ...
1
vote
1answer
144 views

Suppose $G$ is $2$-connected. Show that there exists a path from $x$ to $y$ containing $z$.

I'm studying for a graph theory exam and am stumped on one of the practice questions: Suppose $G$ is $2$-vertex-connected. Show that for any distinct vertices $x$, $y$, $z$ of $G$ there exists a ...
1
vote
2answers
283 views

Partial latin square with $\le n-1$ filled cells

How do we show that is $P$ if a $n\times n$ Latin square with $\le n-1$ filled cells, then $P$ can be completed to a proper Latin square? Here is the definition of a Latin square. (WHAT I HAVE DONE ...
1
vote
2answers
258 views

A combinatorial problem of counting closed walks on grid

Consider an arbitrarily large $N \times N$ grid graph. How can I express the number of closed walks starting from a reference vertex $v$ in terms of the length $L$ of the walk? For example, for $L = ...
1
vote
2answers
286 views

Is the dual graph simple?

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with $n\geq 0$ handles), one can define a dual ...
1
vote
1answer
82 views

Consequences of Hamilton Paths and Cycles

I'm having a bit of trouble with this homework problem: If $G=(V, E)$ is a connected bipartite undirected graph with $V$ partitioned as $V_1\cup V_2$, how can I prove the existence of a Hamilton path ...
1
vote
2answers
204 views

Ramsey theory - colouring of edges

I'm trying to understand a proof: $R(3,3) = 6$ proof: Take a red/blue colouring of $K_6$. Take a vertex $v$ (is an element of) $V(K_6)$, either $v$ is incident to $\geq 3$ red edges or, $v$ is ...
1
vote
2answers
77 views

Set Partitions and Graph Matchings

Is there a standard text on the theory of set partitions and/or graph matchings? (I ask both in the same question since it seems feasible that there might be texts containing information on both.) I ...
1
vote
1answer
131 views

How many nodes before k-clique or k-anti-clique?

I am attempting to solve some problems here. For exercise 1, the tightest result I could get is $4^k$. Is that the mininum possible bound? I am trying to either find a tight example, or find a better ...
1
vote
1answer
393 views

Paths in a full graph

Given a complete graph with $4$ nodes, and one node is labeled $X$, find how many paths of length $N$ (might visit a node more than once) begin, end or both begin and end with $X$. This is not a ...
1
vote
3answers
2k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...
1
vote
1answer
248 views

Is a line considered a face in graph theory?

Is a line considered a face in graph theory? For example just a straight line point to point. 0-------------------------0
1
vote
1answer
179 views

“Almost matching” using Tutte's Theorem

Got pretty strange question in the HW: $G$ is a connected, simple graph with $|E(G)|$ even. I need to prove that there exist a partition of edges into pairwise disjoint pairs, where each pair is ...
1
vote
1answer
72 views

Every $t$-coloring of $K_{2t+1}$ contains a monochromatic cycle

I need help in the following question: I need to prove that in all possible coloring with $t$ colors of the complete graph $K$ with $2t+1$ vertices, there will always be a monochromatic cycle (its ...
1
vote
1answer
675 views

Example of Edge-transitive

I'm looking for graph $G$ such that $G$ is edge-transitive but $G^c$ is not edge-transitive. My conjecture:If $G$ is edge-transitive then $G^c$ is edge-transitive Please advise me.
1
vote
2answers
70 views

Minimum size of a subset to know a complete total order

Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered. $<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$ Given that $<$ is transitive, it ...
1
vote
1answer
421 views

The relation between graph automorphism representation and adjacency matrix of a graph

Given a graph G with adjacency matrix A, the set of automorphisms of G is precisely those permutations which preserve every eigenspace of A. Suppose we examine the restriction of the ...
1
vote
2answers
888 views

Proof of the number of nodes in a finite projective plane

A finite projective plane is a hypergraph in which 1. Any two edges shere exactly one node 2. There is exactly one edge containing any given pair of nodes 3. You can choose 4 nodes such that no three ...
1
vote
1answer
188 views

Conflicting Node Matching Problem

I am trying to figure out the following graph problem, and the best way to solve it. I have a set of n nodes, which represent foods. One or two foods can be eaten each meal, but some pairs of foods ...
1
vote
1answer
75 views

Degree of girraphs

A girraph is an infinite, regular, vertex-transitive graph, on which a random walk is recurrent. The random walk on the square grid returns to the origin with probability 1, and for the cubic grid ...
1
vote
1answer
269 views

If an edge belongs to every minimum spanning tree of $G$, is it a cut edge in $G$?

Basically what the title says. Suppose an edge e is in every minimum spanning tree of G, does that means that e is a cut edge in G? Can I just find a counter example using the contraposition to solve ...
1
vote
1answer
129 views

Partition problem of set

Let $A ={1, 2, 3,..., 100}$. We partition $A$ into $10$ subsets $A_1;A_2;...;A_{10}$ each of size 10. A second partition into 10 sets of size 10 each is given by $B_1;B_2;...;B_{10}$. Prove that we ...
1
vote
1answer
399 views

Transition matrix

I have a directed graph $G_1$. I extract its transition matrix $T_1$. Now I also have directed graph $G_2$, which is equal to $G_1$ with inverted edges. If I get its transition matrix $T_2$, what is ...
1
vote
1answer
423 views

Planar graph embedding algorithm

I'm looking for a planar graph embedding algorithm description. Actually, it would be nice if I knew at least names of these algorithms. The only one I know is called γ(gamma)-algorithm, and it has an ...
1
vote
1answer
210 views

Proof for Matroids: Independence Oracle is polynomial equivalent to Basis Super-Set Oracle

Task: Given an Independence Oracle and a Basis Super-Set Oracle I want to proove, that they are polynomial equivalent for Matroids. First I tried to update my knowledge about the topic. Let ...
1
vote
2answers
2k views

How many non-isomorphic graphs with $5$ vertices and $3$ edges are there?

how many non-isomorphic graphs are there with 5 vertices and 3 edges?
1
vote
1answer
279 views

eigen decomposition of an interesting matrix (general case)

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
1
vote
2answers
1k views

What is a 2-regular graph?

What is a 2-regular graph? Is is the same thing as an 2-connected graph where a 2-connected graph is a graph G such that G-V ( G minus a vertex V) is still connected?
1
vote
1answer
294 views

Eulerian graphs proof

Let G=(V,E) be a connex graph. Color it's edges randomly with red/blue. -prove that there exists an Eulerian circuit, without any two adjacent edges of the same color.. only if for any ...
1
vote
2answers
433 views

complete $k$-ary tree: average distance between all vertices

I am trying to calculate the average distance between all vertices of a complete $k$-ary tree. A complete $k$-ary tree is a tree such that all vertices have $k$ children except for the leafs of the ...
1
vote
1answer
37 views

Graph with exactly one perfect matching

How do I prove that if $ G $ graph, with $2n$ vertices, has exactly one perfect matching then $ |E(G)| \le n^2 $ ?
1
vote
1answer
42 views

Describe 3-colourable graph in propositional calculus

I am trying to solve the following problem. Let $G=(V,E)$ be a Graph with $V=N$ (natural numbers) and $p_{ij}$ a set of propositional variables for which we have $p_{ij}$ is true <=> $(i,j)\in E$. ...
1
vote
2answers
29 views

Prove that a simple graph $G$ on $n$ vertices that contains no $K_{2,3}$ has at most $n^{3/2}$ edges.

For each vertex $v_i$, let $N(v_i)$ denote the set of neighbors of $v_i$. Because $G$ does not contain $K_{2,3}$, equivalently we have $|N(v_i) \cap N(v_j)| \leq 2$ for any $i \neq j$. We need to ...
1
vote
1answer
31 views

How do I know the fundamental group of an infinite graph is well defined?

I get that given a choice of spanning tree and base point for a (connected) graph, I can effectively change the base point through path conjugation, so there's no problem there. For finite graphs, the ...
1
vote
1answer
31 views

What is a useful starting idea to think about this simple graph problem?

I would like to prove the statement that there are $2^{\binom{n-1}{2}}$ simple graphs are there with vertex set $\{1,\ldots,n\}$ such that every vertex has even degree. The thing that confuses me is ...
1
vote
1answer
13 views

How Many Marriages in a Bipartite Graphs?

Given two disjoint sets, say $M$ and $W$, both of size $n$, I want to compute how many possibilities of marriage exist. For example, when $n=1$, there are two marriages only: either $m_1-w_1$ or ...
1
vote
1answer
16 views

Every almost $r$-regular graph has a spanning almost $(r-1)$-regular subgraph

Definition. A Graph is almost $r$-regular if each vertex has degree $r-1$ or $r$. Theorem. Let $G$ be almost $r$-regular for $r\geq 2$, then $G$ contains an almost $(r-1)$-regular graph $H$ with ...
1
vote
1answer
34 views

For every pair $n,d$ such that $d \ge (n-1)/2$ prove that $G$ on $n$ vertices with minimum degree $d$ is edge d-connected.

For every pair $n,d$ such that $d \ge (n-1)/2$ prove that $G$ on $n$ vertices with minimum degree $d$ is edge d-connected. None of my observations I was able to obtain seem to be useful. I am just ...